Shuang Wang
Skip Abstract Section
Abstract
We present PPQ-trajectory, a spatio-temporal quantization based solution for querying large dynamic trajectory data. PPQ-trajectory includes a partition-wise predictive quantizer (PPQ) that generates an error-bounded codebook with autocorrelation and spatial proximity-based partitions. The codebook is indexed to run approximate and exact spatio-temporal queries over compressed trajectories. PPQ-trajectory includes a coordinate quadtree coding for the codebook with support for exact queries. An incremental temporal partition-based index is utilised to avoid full reconstruction of trajectories during queries. An extensive set of experimental results for spatio-temporal queries on real trajectory datasets is presented. PPQ-trajectory shows significant improvements over the alternatives with respect to several performance measures, including the accuracy of results when the summary is used directly to provide approximate query results, the spatial deviation with which spatio-temporal path queries can be answered when the summary is used as an index, and the time taken to construct the summary. Superior results on the quality of the summary and the compression ratio are also demonstrated.
- Fatih Altiparmak, Ertem Tuncel, and Hakan Ferhatosmanoglu. 2007. Incremental maintenance of online summaries over multiple streams. IEEE Transactions on Knowledge and Data Engineering 20, 2 (2007), 216--229. Google Scholar
Digital Library
- Richard E Bellman and Stuart E Dreyfus. 2015. Applied dynamic programming. Vol. 2050. Princeton university press.Google Scholar
- Yuhan Cai and Raymond Ng. 2004. Indexing spatio-temporal trajectories with Chebyshev polynomials. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data. 599--610. Google ScholarDigital Library
- Zhi Cai, Fujie Ren, Juncheng Chen, and Zhiming Ding. 2017. Vector-based trajectory storage and query for intelligent transport system. IEEE Transactions on Intelligent Transportation Systems 19, 5 (2017), 1508--1519. Google ScholarDigital Library
- Addison Chan and Frederick WB Li. 2012. Utilizing massive spatiotemporal samples for efficient and accurate trajectory prediction. IEEE Transactions on Mobile Computing 12, 12 (2012), 2346--2359. Google ScholarDigital Library
- Kang-Tsung Chang. 2008. Introduction to geographic information systems. Vol. 4. McGraw-Hill Boston.Google Scholar
- Minjie Chen, Mantao Xu, and Pasi Franti. 2012. Compression of GPS trajectories. In 2012 Data Compression Conference. IEEE, 62--71. Google ScholarDigital Library
- Yongjian Chen, Tao Guan, and Cheng Wang. 2010. Approximate nearest neighbor search by residual vector quantization. Sensors 10, 12 (2010), 11259--11273.Google ScholarCross Ref
- Jonathan D Cryer and Natalie Kellet. 1991. Time series analysis. Springer. Google ScholarDigital Library
- Philippe Cudre-Mauroux, Eugene Wu, and Samuel Madden. 2010. Trajstore: An adaptive storage system for very large trajectory data sets. In 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010). IEEE, 109--120.Google ScholarCross Ref
- ECML-PKDD. 2015. Taxi Service Trajectory Prediction Challenge 2015. http://www.geolink.pt/ecmlpkdd2015-challenge/Google Scholar
- Hakan Ferhatosmanoglu, Ertem Tuncel, Divyakant Agrawal, and Amr El Abbadi. 2000. Vector approximation based indexing for non-uniform high dimensional data sets. In Proceedings of the ninth international conference on Information and knowledge management. 202--209. Google ScholarDigital Library
- Alyson K Fletcher, Sundeep Rangan, Vivek K Goyal, and Kannan Ramchandran. 2007. Robust predictive quantization: Analysis and design via convex optimization. IEEE Journal of selected topics in signal processing 1, 4 (2007), 618--632.Google ScholarCross Ref
- Stefan Funke, Tobias Rupp, André Nusser, and Sabine Storandt. 2019. PATHFINDER: storage and indexing of massive trajectory sets. In Proceedings of the 16th International Symposium on Spatial and Temporal Databases. 90--99. Google ScholarDigital Library
- Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2946--2953. Google ScholarDigital Library
- Allen Gersho and Robert M Gray. 2012. Vector quantization and signal compression. Vol. 159. Springer Science & Business Media.Google Scholar
- Kevin Gourley and Douglas Green. 1983. A polygon-to-rectangle conversion algorithm. IEEE Computer Graphics and Applications 1 (1983), 31--36. Google ScholarDigital Library
- Yunheng Han, Weiwei Sun, and Baihua Zheng. 2017. COMPRESS: A comprehensive framework of trajectory compression in road networks. ACM Transactions on Database Systems (TODS) 42, 2 (2017), 11. Google ScholarDigital Library
- Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117--128. Google ScholarDigital Library
- Georgios Kellaris, Nikos Pelekis, and Yannis Theodoridis. 2013. Map-matched trajectory compression. Journal of Systems and Software 86, 6 (2013), 1566--1579. Google ScholarDigital Library
- Satoshi Koide, Yukihiro Tadokoro, Takayoshi Yoshimura, Chuan Xiao, and Yoshiharu Ishikawa. 2018. Enhanced Indexing and Querying of Trajectories in Road Networks via String Algorithms. ACM Transactions on Spatial Algorithms and Systems (TSAS) 4, 1 (2018), 3. Google ScholarDigital Library
- Daniel Lemire and Leonid Boytsov. 2015. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45, 1 (2015), 1--29. Google ScholarDigital Library
- Xiucheng Li, Kaiqi Zhao, Gao Cong, Christian S Jensen, and Wei Wei. 2018. Deep representation learning for trajectory similarity computation. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 617--628.Google ScholarCross Ref
- Zhisheng Li, Ken CK Lee, Baihua Zheng, Wang-Chien Lee, Dik Lee, and Xufa Wang. 2010. Ir-tree: An efficient index for geographic document search. IEEE Transactions on Knowledge and Data Engineering 23, 4 (2010), 585--599. Google ScholarDigital Library
- Jiajun Liu, Kun Zhao, Philipp Sommer, Shuo Shang, Brano Kusy, and Raja Jurdak. 2015. Bounded quadrant system: Error-bounded trajectory compression on the go. In 2015 IEEE 31st International Conference on Data Engineering. IEEE, 987--998.Google ScholarCross Ref
- Jiajun Liu, Kun Zhao, Philipp Sommer, Shuo Shang, Brano Kusy, Jae-Gil Lee, and Raja Jurdak. 2016. A novel framework for online amnesic trajectory compression in resource-constrained environments. IEEE Transactions on Knowledge and Data Engineering 28, 11 (2016), 2827--2841. Google ScholarDigital Library
- Xiaoyan Liu and Hakan Ferhatosmanoglu. 2003. Efficient k-NN search on streaming data series. In International Symposium on Spatial and Temporal Databases. Springer, 83--101.Google ScholarCross Ref
- Stuart Lloyd. 1982. Least squares quantization in PCM. IEEE transactions on information theory 28, 2 (1982), 129--137. Google ScholarDigital Library
- Chengjiao Lv, Feng Chen, Yongzhi Xu, Junping Song, and Pin Lv. 2015. A trajectory compression algorithm based on non-uniform quantization. In 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). IEEE, 2469--2474.Google Scholar
- Jonathan Muckell, Jeong-Hyon Hwang, Vikram Patil, Catherine T Lawson, Fan Ping, and SS Ravi. 2011. SQUISH: an online approach for GPS trajectory compression. In Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications. 1--8. Google ScholarDigital Library
- Jonathan Muckell, Paul W Olsen, Jeong-Hyon Hwang, Catherine T Lawson, and SS Ravi. 2014. Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica 18, 3 (2014), 435--460. Google ScholarDigital Library
- Zhaolong Ning, Jun Huang, and Xiaojie Wang. 2019. Vehicular fog computing: Enabling real-time traffic management for smart cities. IEEE Wireless Communications 26, 1 (2019), 87--93.Google ScholarCross Ref
- Mohammad Norouzi and David J Fleet. 2013. Cartesian k-means. In Proceedings of the IEEE Conference on computer Vision and Pattern Recognition. 3017--3024. Google ScholarDigital Library
- Athanasios Papoulis and S Unnikrishna Pillai. 2002. Probability, random variables, and stochastic processes. Tata McGraw-Hill Education.Google Scholar
- Jignesh M Patel, Yun Chen, and V Prasad Chakka. 2004. STRIPES: an efficient index for predicted trajectories. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data. 635--646. Google ScholarDigital Library
- Iulian Sandu Popa, Karine Zeitouni, Vincent Oria, and Ahmed Kharrat. 2015. Spatio-temporal compression of trajectories in road networks. GeoInformatica 19, 1 (2015), 117--145. Google ScholarDigital Library
- Hanan Samet. 1984. The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR) 16, 2 (1984), 187--260. Google ScholarDigital Library
- Renchu Song, Weiwei Sun, Baihua Zheng, and Yu Zheng. 2014. PRESS: A novel framework of trajectory compression in road networks. Proceedings of the VLDB Endowment 7, 9 (2014), 661--672. Google ScholarDigital Library
- Waldo R Tobler. 1979. Cellular geography. In Philosophy in geography. Springer, 379--386.Google Scholar
- Ertem Tuncel, Hakan Ferhatosmanoglu, and Kenneth Rose. 2002. VQ-index: An index structure for similarity searching in multimedia databases. In Proceedings of the tenth ACM international conference on Multimedia. ACM, 543--552. Google ScholarDigital Library
- Sheng Wang, Zhifeng Bao, J Shane Culpepper, Timos Sellis, Mark Sanderson, and Xiaolin Qin. 2017. Answering top-k exemplar trajectory queries. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 597--608.Google ScholarCross Ref
- Sheng Wang, Zhifeng Bao, J Shane Culpepper, Zizhe Xie, Qizhi Liu, and Xiaolin Qin. 2018. Torch: A Search Engine for Trajectory Data.. In SIGIR. 535--544. Google ScholarDigital Library
- Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, Vol. 98. 194--205. Google ScholarDigital Library
- Yan Zhao, Shuo Shang, Yu Wang, Bolong Zheng, Quoc Viet Hung Nguyen, and Kai Zheng. 2018. Rest: A reference-based framework for spatio-temporal trajectory compression. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2797--2806. Google ScholarDigital Library
- Kai Zheng, Yan Zhao, Defu Lian, Bolong Zheng, Guanfeng Liu, and Xiaofang Zhou. 2019. Reference-based framework for spatio-temporal trajectory compression and query processing. IEEE Transactions on Knowledge and Data Engineering (2019).Google Scholar
- Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. 2009. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of the 18th international conference on World wide web. ACM, 791--800. Google ScholarDigital Library
Recommendations
Sampling Big Trajectory Data
CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge ManagementThe increasing prevalence of sensors and mobile devices has led to an explosive increase of the scale of spatio-temporal data in the form of trajectories. A trajectory aggregate query, as a fundamental functionality for measuring trajectory data, aims ...
Time relaxed spatiotemporal trajectory joins
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systemsMany spatiotemporal applications store moving object data in the form of trajectories. Various recent works have addressed interesting queries on trajectorial data, mainly focusing on range queries and Nearest Neighbor queries. Here we examine another ...
Compressing large scale urban trajectory data
CloudDP '14: Proceedings of the Fourth International Workshop on Cloud Data and PlatformsWith the increasing size of trajectory data generated by location-based services and applications which are built from inexpensive GPS-enabled devices in urban environments, the need for compressing large scale trajectories becomes obvious. This paper ...
Comments