Compression and Mining of GPS Trace Data: New Techniques and Applications

2011Final Report January 1, 2010 - December 31, 2010PDFTech ReportGlobal Positioning SystemCompressionTrajectoryspatial algorithms,error metricsNew YorkUnited StatesCity University of New York. University Transportation Research CenterLawson, Catherine T.Ravi, Sekharipuram S.Hwang, Jeong-HyonUniversity Transportation Research CenterState University of New York at AlbanyUnited States. Federal Highway AdministrationUS Transportation CollectionThe massive volumes of trajectory data generated by inexpensive GPS devices have led to difficulties in processing, querying, transmitting and storing such data. To overcome these difficulties, a number of algorithms for compressing trajectory data have been proposed. These algorithms try to reduce the size of trajectory data, while preserving the quality of the information. We present results from a comprehensive empirical evaluation of many compression algorithms including Douglas-Peucker Algorithm, Bellman's Algorithm, STTrace Algorithm and Opening Window Algorithms. Our empirical study uses different types of real-world data such as pedestrian, vehicle and multimodal trajectories. The algorithms are compared using several criteria including how well they preserve the spatiotemporal information across numerous real-world datasets, execution times and various error metrics. Such comparisons are useful in identifying the most effective algorithms for various situations. We also provide recommendations for a hybrid algorithm which can leverage the strengths of various algorithms while mitigating their drawbacks.78