PRESS: A Novel Framework of Trajectory Compression in Road Networks

Preprint English OPEN
Song, Renchu ; Sun, Weiwei ; Zheng, Baihua ; Zheng, Yu (2014)
  • Subject: Computer Science - Databases

Location data becomes more and more important. In this paper, we focus on the trajectory data, and propose a new framework, namely PRESS (Paralleled Road-Network-Based Trajectory Compression), to effectively compress trajectory data under road network constraints. Different from existing work, PRESS proposes a novel representation for trajectories to separate the spatial representation of a trajectory from the temporal representation, and proposes a Hybrid Spatial Compression (HSC) algorithm and error Bounded Temporal Compression (BTC) algorithm to compress the spatial and temporal information of trajectories respectively. PRESS also supports common spatial-temporal queries without fully decompressing the data. Through an extensive experimental study on real trajectory dataset, PRESS significantly outperforms existing approaches in terms of saving storage cost of trajectory data with bounded errors.
  • References (20)
    20 references, page 1 of 2

    [1] Alfred V. Aho and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search. CACM, 18(6):333-340, 1975.

    [2] Richard Bellman. On the approximation of curves by line segments using dynamic programming. CACM, 4(6):284, 1961.

    [3] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In VLDB'05, pages 853-864, 2005.

    [4] Hu Cao and Ouri Wolfson. Nonmaterialized motion information in transport networks. In ICDT'05, pages 173-188, 2005.

    [5] David H. Douglas and Thomas K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica, 10(2):112-122, 1973.

    [6] Jiawei Han, Micheline Kamber, and Jian Pei. Data mining: concepts and techniques. Morgan Kaufmann, 2006.

    [7] John Edward Hershberger and Jack Snoeyink. Speeding up the Douglas-Peucker line-simplification algorithm. University of British Columbia, Department of Computer Science, 1992.

    [8] David A. Huffman. A method for the construction of minimum-redundancy codes. IRE, 40(9):1098- 1101, 1952.

    [9] Donald E. Kauth. The art of computer programming: Volume 3/Sorting and searching. Addison-Wesley, 1973.

    [10] Georgios Kellaris, Nikos Pelekis, and Yannis Theodoridis. Map-matched trajectory compression. JSS, 86(6):1566-1579, 2013.

  • Related Research Results (1)
  • Metrics
    No metrics available
Share - Bookmark