Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2017

Abstract

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.

Keywords

GPS trajectory, road network, trajectory compression, map-matching, information entropy, trajectory representation, entropy encoding, dictionary coder, stabbing polyline

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

ACM Transactions on Database Systems

Volume

42

Issue

2

First Page

11: 1

Last Page

45

ISSN

0362-5915

Identifier

10.1145/3015457

Publisher

Association for Computing Machinery (ACM)

Copyright Owner and License

LARC and Authors

Additional URL

https://doi.org/10.1145/3015457

Download

Share

COinS