测绘学报 ›› 2023, Vol. 52 ›› Issue (3): 501-514.doi: 10.11947/j.AGCS.2023.20210614
赵东保1, 邓悦1,2
收稿日期:
2021-11-10
修回日期:
2022-11-26
发布日期:
2023-04-07
作者简介:
赵东保(1979-),男,博士,教授,研究方向为空间数据融合与挖掘。E-mail:zdongbao@126.com
基金资助:
ZHAO Dongbao1, DENG Yue1,2
Received:
2021-11-10
Revised:
2022-11-26
Published:
2023-04-07
Supported by:
摘要: 基于位置服务技术的迅猛发展,产生了巨量车辆轨迹数据。为了有效压缩并查询大规模车辆轨迹数据,本文提出一种面向压缩车辆轨迹的路径空间查询算法。本文算法基于Stroke道路层次结构压缩轨迹空间数据,提取关键变速点压缩轨迹时间数据,并构建了一种用于建立轨迹空间和时间数据之间联系的哈希编码,从而实现车辆轨迹的时空数据集成压缩。利用后缀数组对车辆轨迹的基于Stroke路段的压缩编码构建空间索引结构,再以此为基础,设计了车辆轨迹所对应路径的点信息查询算法、相同子路径查询算法和相似路径查询算法。试验结果表明,针对原始轨迹点空间数据,本文的压缩编码方法压缩比可以达到97∶1,与常规的基于路段编码方式相比,本文压缩编码在车辆轨迹的点信息路径查询方面,查询效率可以提升约2倍;在车辆轨迹的相同子路径查询方面,查询效率可以提升约8倍;在车辆轨迹的相似路径查询方面,查询耗时增长率减少了50%。本文算法对于大规模车辆轨迹的数据管理具有十分重要的基础性作用。
中图分类号:
赵东保, 邓悦. 顾及轨迹压缩的车辆路径查询算法[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. |
[1] | 吴华意, 胡秋实, 李锐, 刘朝辉. 城市人口时空分布估计研究进展[J]. 测绘学报, 2022, 51(9): 1827-1847. |
[2] | 刘经南, 罗亚荣, 郭迟, 高柯夫. PNT智能与智能PNT[J]. 测绘学报, 2022, 51(6): 811-828. |
[3] | 韩李涛, 周丽娟, 龚城, 张爱国. 顾及步行习惯的室内导航网络及其生成算法[J]. 测绘学报, 2022, 51(5): 729-738. |
[4] | 方金凤, 孟祥福. 基于LBSN和多图融合的兴趣点推荐[J]. 测绘学报, 2022, 51(5): 739-749. |
[5] | 张睿卓. 基于多源数据的林区电力走廊安全风险评估方法[J]. 测绘学报, 2022, 51(5): 784-784. |
[6] | 夏吉喆, 周颖, 李珍, 李帆, 乐阳, 程涛, 李清泉. 城市时空大数据驱动的新型冠状病毒传播风险评估——以粤港澳大湾区为例[J]. 测绘学报, 2020, 49(6): 671-680. |
[7] | 朱庆, 冯斌, 李茂粟, 陈媚特, 徐肇文, 谢潇, 张叶廷, 刘铭崴, 黄志勤, 冯义从. 面向动态关联数据的高效稀疏图索引方法[J]. 测绘学报, 2020, 49(6): 681-691. |
[8] | 陆川伟, 孙群, 陈冰, 温伯威, 赵云鹏, 徐立. 车辆轨迹数据的道路学习提取法[J]. 测绘学报, 2020, 49(6): 692-702. |
[9] | 尹烁, 闫小明, 晏雄锋. 基于特征边重构的建筑物化简方法[J]. 测绘学报, 2020, 49(6): 703-710. |
[10] | 吴华意, 黄蕊, 游兰, 向隆刚. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11): 1341-1356. |
[11] | 郭庆胜, 刘洋, 李萌, 程晓茜, 何捷, 王慧慧, 魏智威. 基于网格模型的导航道路图渐进式化简方法[J]. 测绘学报, 2019, 48(11): 1357-1368. |
[12] | 吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379. |
[13] | 王培晓, 张恒才, 王海波, 吴升. ST-CFSFDP:快速搜索密度峰值的时空聚类算法[J]. 测绘学报, 2019, 48(11): 1380-1390. |
[14] | 万子健, 李连营, 杨敏, 周校东. 车辆轨迹数据提取道路交叉口特征的决策树模型[J]. 测绘学报, 2019, 48(11): 1391-1403. |
[15] | 胡光辉, 熊礼阳, 汤国安. DEM地表坡向变率的向量几何计算法[J]. 测绘学报, 2019, 48(11): 1404-1414. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||