COMPRESS: A comprehensive framework of trajectory compression in road networks

• Main Authors: HAN, Yunheng, SUN, Weiwei, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: GPS trajectory; road network; trajectory compression; map-matching; information entropy; trajectory representation; entropy encoding; dictionary coder; stabbing polyline; Databases and Information Systems; Numerical Analysis and Scientific Computing; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/3647; https://ink.library.smu.edu.sg/context/sis_research/article/4649/viewcontent/4._Nov04___COMPRESS_A_Comprehensive_Framework_of_Trajectory__ACM_TODS2016__JOURNALpaper.pdf
• Institution: Singapore Management University

More and more advanced technologies have become available to collect and integrate an unprecedented amount of data from multiple sources, including GPS trajectories about the traces of moving objects. Given the fact that GPS trajectories are vast in size while the information carried by the trajectories could be redundant, we focus on trajectory compression in this article. As a systematic solution, we propose a comprehensive framework, namely, COMPRESS (Comprehensive Paralleled Road-Network-Based Trajectory Compression), to compress GPS trajectory data in an urban road network. In the preprocessing step, COMPRESS decomposes trajectories into spatial paths and temporal sequences, with a thorough justification for trajectory decomposition. In the compression step, COMPRESS performs spatial compression on spatial paths, and temporal compression on temporal sequences in parallel. It introduces two alternative algorithms with different strengths for lossless spatial compression and designs lossy but error-bounded algorithms for temporal compression. It also presents query processing algorithms to support error-bounded location-based queries on compressed trajectories without full decompression. All algorithms under COMPRESS are efficient and have the time complexity of O(|T|), where |T| is the size of the input trajectory T. We have also conducted a comprehensive experimental study to demonstrate the effectiveness of COMPRESS, whose compression ratio is significantly better than related approaches.