Trajectory Simplification Algorithm based on Structure Features
Abstract
With the extensive use of location based devices, trajectories of various kind of moving objects can be collected. As time going on, the amount of trajectory data increases exponentially, which brings a series of problems in storage, transmission and analysis. Current trajectory compression algorithms mainly focus on position preserving, compress ratio and run efficiency, but neglect the movement features in trajectories. In this paper, we propose a novel three-stage trajectory compression algorithm based on moving direction of objects, internal fluctuation in trajectories and trajectory velocity, which takes full account of movement pattern and structure features in trajectories. Firstly, the raw trajectory is compressed based on moving direction and the velocity of the object. Then, the trajectory is further simplified according to internal fluctuation in raw trajectory. Comprehensive experiments on real dataset show that: not only the efficiency and effectiveness of the proposed work is better, but also the reservation of local movement features of moving objects and internal characteristic information in trajectories is more detailed.
Downloads
References
Minjie Chen, Mantao Xu, Pasi Franti. Compression of GPS trajectories. In: Proceedings of the 2012 Data Compression Conference (DCC 2012), April 10-12, 2012, Snowbird, Utah, USA, 62-71.
Nirvana Meratnia, Rolf A. de By. Spatiotemporal compression techniques for moving point objects. In: Proceedings of the 9th International Conference on Extending Database Technology (EDBT 2004), March 14-18, 2004, Crete, Greece, 765-782.
Xiaoying Liu. Trajectory data compression via spatial-temporal properties. Master Degree Thesis, Hong Kong University of Science and Technology, 2014, Hong Kong, China.
Douglas H David, Peucker K Thomas. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.
Michalis Potamias, Kostas Patroumpas, Timos Sellis. Sampling trajectory streams with spatiotemporal criteria. In: Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM 2006). July 3-5, 2006, Vienna, Austria, 275-284.
Jianjun Liu, Kun Zhao, Philipp Sommer, et al. Bounded quadrant system: error-bounded trajectory compression on the go. In: Proceedings of the 31th IEEE International Conference on Data Engineering (ICDE 2015), March 31-April 4, 2015, Seoul, Korea, 987-998.
Birnbaum J, Meng H C, Hwang J H, et al. Similarity-based compression of GPS trajectory data. In: Proceedings of the 4nd International Conference on Computing for Geospatial Research & Applications (COM. Geo 2013), July 22-24, 2013, San Jose, CA, USA, 92-95.
Cheng Long, Raymond Chi-Wing Wong, H. V. Jagadish. Direction-preserving trajectory simplification. Proceedings of the VLDB Endowment, 2013, 6(10): 949-960.
Jae-Gil Lee, Jiawei Han, Xiaolei Li. Trajectory outlier detection: A partition-and-detect framework. In: Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE 2008). April 7-12, 2008, Cancún, México, 140-149.
Jae-Gil Lee, Jiawei Han, Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (SIGMOD 2007). June 11-14, 2007, Beijing, China, 593-604.
Guan Yuan, Shixiong Xia, Lei Zhang, Yong Zhou and Cheng Ji. An efficient trajectory-clustering algorithm based on an index tree. Transaction of the Institute of Measurement and Control 2012, 34(7):850-861.
Aiden Nibali, Zhen He. Trajic: An effective compression system for trajectory data. IEEE Transaction on Knowledge and Data Engineering, 2015, 27(11):3138-3151.
Rajib Rana, Mingrui Yang, Tim Wark, et al. SimpleTrack: Adaptive trajectory compression with deterministic projection matrix for mobile sensor networks. IEEE Sensors Journal, 2015, 15(1): 365-373.
Kuien Liu, Yaguang Li, Jian Dai, Shuo Shang, Kai Zheng. Compressing large scale urban trajectory data. In: Proceedings of the Fourth International Workshop on Cloud Data and Platforms (CloudDP 2014). April 13, 2014, Amsterdam, Netherlands, 3: 1-6.
Renchu Song, Weiwei Sun, Baihua Zheng, Yu Zheng. PRESS: A novel framework of trajectory compression in road networks. Proceedings of the VLDB Endowment, 2014, 7(9): 661-672.
Georgios Kellaris, Nikos Pelekis, Yannis Theodoridis. Map-matched trajectory compression. Journal of Systems and Software, 2013, 86(6): 1566-1579.
Iulian Sandu Popa, Karine Zeitouni, Vincent Oria, et al. Spatio-temporal compression of trajectories in road networks. GeoInformatica, 2014, 19(1): 117-145.
Falko Schmid, Kai-Florian Richter, Patrick Laube. Semantic trajectory compression. In: Proceedings of the 11the International Symposium on Spatial and Temporal Databases (SSTD 2009). July 8-10, 2009, Aalborg, Denmark, 411-416.
Richter K F, Schmid F, Laube P. Semantic trajectory compression: Representing urban movement in a nutshell. Journal of Spatial Information Science, 2015 (4): 3-30.
Shenzhu Feng, Jian Xu Ming, Xu Ning Zheng, et al. EHSTC: an enhanced method for semantic trajectory compression. In: Proceedings of the 4th ACM SIGSPATIAL International Workshop on GeoStreaming (IWGS 2013). November 5, 2013, Orlando, Florida, USA, 43-49.
Jonathan Muckell, Jeong-Hyon Hwang, Vikram Patil, et al. SQUISH: an online approach for GPS trajectory compression. In: Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications (COM. Geo 2011). Article number: 13, 1-8.
Jonathan Muckell, Paul W, Olsen Jr., Jeong-Hyon Hwang, et al. Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica, 2014, 18(3): 435-460.
Guangwen Liu, Masayuki Iwai, Kaoru Sezaki. A method for online trajectory simplification by enclosed area metric. In: Proceedings of the 6th International Conference on Mobile Computing and Ubiquitous Networking, May 23 - 24, 2012, Okinawa Japan, 40-47.
Guangwen Liu, Masayuki Iwai, Kaoru Sezaki. An online method for trajectory simplification under uncertainty of gps. IPSJ Transactions on Databases, 2013, 6(3): 40-49.
Wei Pan, Chunlong Yao, Xu Li, Lan Shen. An online compression algorithm for positioning data acquisition. Informatica, 2014, 38(4):339-346.
Trajcevski G, Cao H, Scheuermanny P, et al. On-line data reduction and the quality of history in moving objects databases[C]//Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access. ACM, 2006: 19-26.
Copyright (c) 2019 IJRDO - Journal of Computer Science Engineering (ISSN: 2456-1843)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Author(s) and co-author(s) jointly and severally represent and warrant that the Article is original with the author(s) and does not infringe any copyright or violate any other right of any third parties, and that the Article has not been published elsewhere. Author(s) agree to the terms that the IJRDO Journal will have the full right to remove the published article on any misconduct found in the published article.
