顾及轨迹压缩的车辆路径查询算法

doi:10.11947/j.AGCS.2023.20210614

摘要/Abstract

摘要： 基于位置服务技术的迅猛发展,产生了巨量车辆轨迹数据。为了有效压缩并查询大规模车辆轨迹数据,本文提出一种面向压缩车辆轨迹的路径空间查询算法。本文算法基于Stroke道路层次结构压缩轨迹空间数据,提取关键变速点压缩轨迹时间数据,并构建了一种用于建立轨迹空间和时间数据之间联系的哈希编码,从而实现车辆轨迹的时空数据集成压缩。利用后缀数组对车辆轨迹的基于Stroke路段的压缩编码构建空间索引结构,再以此为基础,设计了车辆轨迹所对应路径的点信息查询算法、相同子路径查询算法和相似路径查询算法。试验结果表明,针对原始轨迹点空间数据,本文的压缩编码方法压缩比可以达到97∶1,与常规的基于路段编码方式相比,本文压缩编码在车辆轨迹的点信息路径查询方面,查询效率可以提升约2倍;在车辆轨迹的相同子路径查询方面,查询效率可以提升约8倍;在车辆轨迹的相似路径查询方面,查询耗时增长率减少了50%。本文算法对于大规模车辆轨迹的数据管理具有十分重要的基础性作用。

关键词: 轨迹压缩, Stroke层次结构, 相同路径查询, 相似路径查询

Abstract: With the rapid development of location-based service technology, a huge amount of vehicle trajectory data has been generated. To effectively compress and query large-scale vehicle trajectory data, this paper proposes a path spatial queries algorithm for compressed vehicle trajectories. The algorithm compresses the spatial data of trajectories based on the Stroke road hierarchical structure, compresses the temporal data of trajectories by extracting the key variable speed points, and constructs a hash coding for establishing the connection between trajectory spatial data and trajectory temporal data, so as to realize the integrated compression of spatio-temporal data of vehicle trajectories. The suffix array is used to construct the spatial index structure of the compression coding based on the Stroke segment of the vehicle trajectories. On this basis, the point information query algorithm, strict path query algorithm and similar path query algorithm of the corresponding path of vehicle trajectories are designed. The experimental results indicate that for the original trajectory point spatial data, the compression ratio of the proposed compression coding method can reach 97∶1. Compared with the conventional road segments-based coding mode, the proposed compression coding method has high path spatial queries performance. In the point information query of the path corresponding to the vehicle trajectory, the query efficiency can be increased by about 2 times. In the strict sub-path query of the vehicle trajectory, the query efficiency can be increased by about 8 times, and the growth rate of the query time is reduced by about 50% in the similar path query of the vehicle trajectory. This method plays a fundamental role in the data management of large-scale vehicle trajectories.

Key words: trajectory compression, Stroke hierarchical structure, strict path query, similar path query

中图分类号:

P208

赵东保, 邓悦. 顾及轨迹压缩的车辆路径查询算法[J]. 测绘学报, 2023, 52(3): 501-514.

ZHAO Dongbao, DENG Yue. Vehicle path queries method considering vehicle trajectory compression[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(3): 501-514.

参考文献

[1] 江俊文, 王晓玲. 轨迹数据压缩综述[J]. 华东师范大学学报(自然科学版), 2015(5):61-76. JIANG Junwen, WANG Xiaoling. Review on trajectory data compression[J]. Journal of East China Normal University (Natural Science), 2015(5):61-76.
[2] SUN Penghui, XIA Shixiong, YUAN Guan, et al. An overview of moving object trajectory compression algorithms[J]. Mathematical Problems in Engineering, 2016, 2016:1-13.
[3] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica:the International Journal for Geographic Information and Geovisualization, 1973, 10(2):112-122.
[4] MERATNIA N, DE BY R A. Spatiotemporal compression techniques for moving point objects[M]//Advances in Database Technology-EDBT 2004. Berlin:Springer, 2004:765-782.
[5] SONG Renchu, SUN Weiwei, ZHENG Baihua, et al. Press[J]. Proceedings of the VLDB Endowment, 2014, 7(9):661-672.
[6] HAN Yunheng, SUN Weiwei, ZHENG Baihua. COMPRESS:a comprehensive framework of trajectory compression in road networks[J]. ACM Transactions on Database Systems, 2017, 42(2):1-49.
[7] ZHAO Dongbao, STEFANAKIS E. Integrated compression of vehicle spatio-temporal trajectories under the road stroke network constraint[J]. Transactions in GIS, 2018, 22(4):991-1007.
[8] CHEN Chao, DING Yan, XIE Xuefeng, et al. TrajCompressor:an online map-matching-based trajectory compression framework leveraging vehicle heading direction and change[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(5):2012-2028.
[9] BIRNBAUM J, MENG H C, HWANG J H, et al. Similarity-based compression of GPS trajectory data[C]//Proceedings of the 4th International Conference on Computing for Geospatial Research and Application. San Jose, CA, USA:IEEE, 2013:92-95.
[10] MAKRIS A, LEITE DA SILVA C, BOGORNY V, et al. Evaluating the effect of compressing algorithms for trajectory similarity and classification problems[J]. Geoinformatica, 2021, 25(4):679-711.
[11] SU Han, ZHENG Kai, ZENG Kai, et al. Making sense of trajectory data:a partition-and-summarization approach[C]//Proceedings of 2015 IEEE International Conference on Data Engineering. Seoul, Korea:IEEE, 2015:963-974.
[12] GAO Chongming, ZHAO Yi, WU Ruizhi, et al. Semantic trajectory compression via multi-resolution synchronization-based clustering[J]. Knowledge-Based Systems, 2019, 174(C):177-193.
[13] DENG Ke, XIE Kexin, ZHENG K, et al. Trajectory indexing and retrieval[M]//Computing with Spatial Trajectories. New York:Springer, 2011:35-60.
[14] MAHMOOD A R, PUNNI S, AREF W G. Spatio-temporal access methods:a survey (2010-2017)[J]. GeoInformatica, 2019, 23(1):1-36.
[15] FRENTZOS E. Indexing objects moving on fixed networks[M]//Advances in Spatial and Temporal Databases. Berlin:Springer, 2003:289-305.
[16] TEIXEIRA DE ALMEIDA V, GVTING R H. Indexing the trajectories of moving objects in networks[J]. GeoInformatica, 2005, 9(1):33-60.
[17] THEODORIDIS Y, SELLIS T, PAPADOPOULOS A N, et al. Specifications for efficient indexing in spatiotemporal databases[C]//Proceedings of the 10th International Conference on Scientific and Statistical Database Management. Capri, Italy:IEEE, 2002:123-132.
[18] SANDU POPA I, ZEITOUNI K, ORIA V, et al. PARINET:a tunable access method for in-network trajectories[C]//Proceedings of 2010 IEEE International Conference on Data Engineering (ICDE 2010). Long Beach, CA, USA:IEEE, 2010:177-188.
[19] PFOSER D, JENSEN C S, THEODORIDIS Y. Novel Approaches to the indexing of moving object trajectories[C]//Proceedings of 2000 Very Large Database Conference. Cairo, Egypt:The Association for Computing Machinery, 2000:395-406.
[20] 丁治明. 一种适合于频繁位置更新的网络受限移动对象轨迹索引[J]. 计算机学报, 2012, 35(7):1448-1461. DING Zhiming. An index structure for frequently updated network-constrained moving object trajectories[J]. Chinese Journal of Computers, 2012, 35(7):1448-1461.
[21] HENDAWI A M, BAO J, MOKBEL M F, et al. Predictive tree:an efficient index for predictive queries on road networks[C]//Proceedings of the 31st International Conference on Data Engineering. Seoul, Karea:IEEE, 2015:1215-1226.
[22] DING Yichen, ZHOU Xun, WU Guojun, et al. Mining spatio-temporal reachable regions with multiple sources over massive trajectory data[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(7):2930-2942.
[23] CHEN Rui, CHEN Mingjian, LI Wanli, et al. Predicting future locations of moving objects by recurrent mixture density network[J]. ISPRS International Journal of Geo-Information, 2020, 9(2):116.
[24] YANG Xiaochun, WANG Bin, YANG Kai, et al. A novel representation and compression for queries on trajectories in road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(4):613-629.
[25] KOIDE S, TADOKORO Y, YOSHIMURA T, et al. CiNCT:compression and retrieval for massive vehicular trajectories via relative movement labeling[C]//Proceedings of the 34th International Conference on Data Engineering. Paris, France:IEEE, 2018:1097-1108.
[26] LIU Yi, LI Wenjing. A new algorithms of Stroke generation considering geometric and structural properties of road network[J]. International Journal of Geo-Information, 2019, 8(7):304.
[27] CHAWATHE S S. Segment-based map matching[C]//Proceedings of 2007 IEEE Intelligent Vehicles Symposium. Istanbul. Ankara, Turkey:IEEE, 2007:1190-1197.
[28] 于娟, 杨琼, 鲁剑锋, 等. 高级地图匹配算法:研究现状和趋势[J]. 电子学报, 2021, 49(9):1818-1829. YU Juan, YANG Qiong, LU Jianfeng, et al. Advanced map matching algorithms:a survey and trends[J]. Acta Electronica Sinica, 2021, 49(9):1818-1829.
[29] 左一萌, 林学练, 马帅, 等. 路网感知的在线轨迹压缩方法[J]. 软件学报, 2018, 29(3):734-755. ZUO Yimeng, LIN Xuelian, MA Shuai, et al. Road network aware online trajectory compression[J]. Journal of Software, 2018, 29(3):734-755.
[30] LI Tianyi, HUANG Ruikai, CHEN Lu, et al. Compression of uncertain trajectories in road networks[J]. Proceedings of the VLDB Endowment, 2020, 13(7):1050-1063.
[31] 付仲良, 翁宝凤, 胡玉龙. Stroke构造、移位一体化的道路网示意化方法[J]. 测绘学报, 2016, 45(9):1115-1121. DOI:10.11947/j.AGCS.2016.20160080. FU Zhongliang, WENG Baofeng, HU Yulong. A schematic method based on the integration of Stroke construction and displacement for road network[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(9):1115-1121. DOI:10.11947/j.AGCS.2016.20160080.
[32] YU Wenhao, ZHANG Yifan, AI Tinghua, et al. Road network generalization considering traffic flow patterns[J]. International Journal of Geographical Information Science, 2020, 34(1):119-149.
[33] 杨敏, 艾廷华, 周启. 顾及道路目标Stroke特征保持的路网自动综合方法[J]. 测绘学报, 2013, 42(4):581-587, 594. YANG Min, AI Tinghua, ZHOU Qi. A method of road network generalization considering Stroke properties of road object[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4):581-587, 594.
[34] LAO Bin, NONG Ge, CHAN Waihong, et al. Fast in-place suffix sorting on a multicore computer[J]. IEEE Transactions on Computers, 2018, 67(12):1737-1749.
[35] SUNDAY D M. A very fast substring search algorithm[J]. Communications of the ACM, 1990, 33(8):132-142.