Renchu Song
Yu Zheng
Abstract
Location data becomes more and more important. In this paper, we focus on the trajectory data, and propose a new framework, namely PRESS (<u>P</u>aralleled <u>R</u>oad-Network-Based Trajectory Compr<u>ess</u>ion), 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.
- Alfred V. Aho and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search. CACM, 18(6):333--340, 1975. Google Scholar
Digital Library
- Richard Bellman. On the approximation of curves by line segments using dynamic programming. CACM, 4(6):284, 1961. Google ScholarDigital Library
- Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In VLDB'05, pages 853--864, 2005. Google ScholarDigital Library
- Hu Cao and Ouri Wolfson. Nonmaterialized motion information in transport networks. In ICDT'05, pages 173--188, 2005. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Jiawei Han, Micheline Kamber, and Jian Pei. Data mining: concepts and techniques. Morgan Kaufmann, 2006. Google ScholarDigital Library
- John Edward Hershberger and Jack Snoeyink. Speeding up the Douglas-Peucker line-simplification algorithm. University of British Columbia, Department of Computer Science, 1992.Google ScholarDigital Library
- David A. Huffman. A method for the construction of minimum-redundancy codes. IRE, 40(9):1098--1101, 1952.Google ScholarCross Ref
- Donald E. Kauth. The art of computer programming: Volume 3/Sorting and searching. Addison-Wesley, 1973.Google Scholar
- Georgios Kellaris, Nikos Pelekis, and Yannis Theodoridis. Map-matched trajectory compression. JSS, 86(6):1566--1579, 2013. Google ScholarDigital Library
- Eamonn Keogh, Selina Chu, David Hart, and Michael Pazzani. An online algorithm for segmenting time series. In ICDM'01, pages 289--296, 2001. Google ScholarDigital Library
- Eamonn J. Keogh and Michael J. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In KDD'98, pages 239--243, 1998.Google Scholar
- Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-matching for low-sampling-rate gps trajectories. In GIS'09, pages 352--361, 2009. Google ScholarDigital Library
- Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M. Ni. Finding time period-based most frequent path in big trajectory data. In SIGMOD'13, pages 713--724, 2013. Google ScholarDigital Library
- Robert B. McMaster. A statistical analysis of mathematical measures for linear simplification. The American Cartographer, 13(2):103--116, 1986.Google ScholarCross Ref
- Nirvana Meratnia and A. Rolf. Spatiotemporal compression techniques for moving point objects. In EDBT'04, pages 765--782, 2004.Google ScholarCross Ref
- Jonathan Muckell, Jeong-Hyon Hwang, Catherine T. Lawson, and S. S. Ravi. Algorithms for compressing gps trajectory data: an empirical evaluation. In GIS'10, pages 402--405, 2010. Google ScholarDigital Library
- Jonathan Muckell, Paul W. Olsen Jr, Jeong-Hyon Hwang, Catherine T. Lawson, and S. S. Ravi. Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica, pages 1--26, Published Online: July, 2013. Google ScholarDigital Library
- Paul Newson and John Krumm. Hidden markov map matching through noise and sparseness. In GIS'09, pages 336--343, 2009. Google ScholarDigital Library
- Michalis Potamias, Kostas Patroumpas, and Timos Sellis. Sampling trajectory streams with spatiotemporal criteria. In SSDBM'06, pages 275--284, 2006. Google ScholarDigital Library
- Renchu Song, Wei Lu, Weiwei Sun, Yan Huang, and Chunan Chen. Quick map matching using multi-core cpus. In GIS'12, pages 605--608, 2012. Google ScholarDigital Library
- Renchu Song, Weiwei Sun, Baihua Zheng, and Yu Zheng. Press: A novel framework of trajectory compression in road networks (http://arxiv.org/abs/1402.1546). Technical report, 2014.Google Scholar
- Goce Trajcevski, Hu Cao, Peter Scheuermanny, Ouri Wolfsonz, and Dennis Vaccaro. On-line data reduction and the quality of history in moving objects databases. In DEWMA'06, pages 19--26, 2006. Google ScholarDigital Library
- Jeffrey S. Vitter. Random sampling with a reservoir. TOMS, 11(1):37--57, 1985. Google ScholarDigital Library
- Raymond Chi-Wing Wong and Ada Wai-Chee Fu. Mining top-k frequent itemsets from data streams. Data Mining and Knowledge Discovery, 13(2):193--217, 2006. Google ScholarDigital Library
- Yu Zheng and Xiaofang Zhou. Computing with spatial trajectories. Springer, 2011. Google ScholarDigital Library
Index Terms
- PRESS: a novel framework of trajectory compression in road networks
Recommendations
Trajectory planning, optimization and control of a hybrid mechanical press
Hybrid mechanical press is an innovative sheet metal stamping press that has the advantages of both mechanical press and the hydraulic press. This paper focuses on the control of the hybrid mechanical press, including trajectory planning, trajectory ...
The hyperdyadic index and generalized indexing and query with PIQUE
SSDBM '15: Proceedings of the 27th International Conference on Scientific and Statistical Database ManagementMany scientists rely on indexing and query to identify trends and anomalies within extreme-scale scientific data. Compressed bitmap indexing (e.g., FastBit) is the go-to indexing method for many scientific datasets and query workloads. Recently, the ...
Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes
Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the ...
Comments