一种融合图结构的时空轨迹相似性查询算法

doi:10.3969/j.issn.0255-8297.2023.01.002

摘要/Abstract

摘要： 针对海量时空轨迹数据相似性查询速度慢的问题，提出一种融合图结构的时空轨迹相似性查询算法。从空间维和时间维将轨迹建模为图结构中的一条路径，设计了一种同步匹配空间和时间距离的轨迹相似性度量函数。在此基础上，设计了一种结合时间过滤的基于边的倒排索引结构支持轨迹时空相似性查询，同时利用距离上界的剪枝策略提高查询性能。计算返回的相似轨迹集合中每条轨迹的距离并进行排序，得到相似度最高的前k个轨迹。最后将所提算法与NTrajI算法、SHQ算法、SHQT算法在合成数据集和真实数据集上进行实验对比。结果表明：该算法在索引建立、查询效率和查询质量方面均优于其他对比方法，因此是可行而有效的。

关键词: 时空轨迹, 轨迹相似性度量, 轨迹相似性查询, 倒排索引, 距离上界

Abstract: To address the problem of slow similarity query of massive spatio-temporal trajectory data, a similarity query algorithm based on graph structure is proposed. Firstly, the trajectory is modeled as a path with spatial and temporal dimensions in a graph, and a trajectory similarity metric function is designed to match spatial and temporal distances simultaneously. Secondly, based on the similarity metric function, an edge-based inverted index structure combined with time filtering is designed, which supports spatio-temporal similarity query of trajectories while improving query performance using a pruning strategy with distance upper bound. The query algorithm performs distance calculation for each trajectory in the returned set of similar trajectories and sorts to obtain the top k results with the highest similarity. Finally, synthetic dataset and real dataset are used to compare the proposed algorithm with NTrajI algorithm, SHQ algorithm and SHQT algorithm. Experimental results show that the proposed method outperforms the comparison methods in index building and query processing, and obtains higher quality of query results. Therefore, the proposed algorithm is feasible and effective.

Key words: spatio-temporal trajectory, trajectory similarity measure, trajectory similarity search, inverted index, distance bounds

中图分类号:

TP301.6

熊伟, 熊淑怡, 曹竞之, 陈浩, 高嘉媛. 一种融合图结构的时空轨迹相似性查询算法[J]. 应用科学学报, 2023, 41(1): 10-22.

XIONG Wei, XIONG Shuyi, CAO Jingzhi, CHEN Hao, GAO Jiayuan. A Spatio-Temporal Similarity Query Algorithm for Trajectory Based on Graph Structure[J]. Journal of Applied Sciences, 2023, 41(1): 10-22.

参考文献

[1] 高强, 张凤荔, 王瑞锦, 等. 轨迹大数据:数据处理关键技术研究综述[J]. 软件学报, 2017, 28(4):959-992. Gao Q, Zhang F L, Wang R J, et al. Trajectory big data:a review of key technologies in data processing[J]. Journal of Software, 2017, 28(4):959-992. (in Chinese)
[2] 吴华意, 黄蕊, 游兰, 等. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11):1341-1356. Wu H Y, Huang R, You L, et al. Recent progress in taxi trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11):1341-1356. (in Chinese)
[3] 章志刚. 面向轨迹大数据的管理及查询研究[D]. 上海:华东师范大学, 2018.
[4] 牟乃夏, 徐玉静, 张恒才, 等. 出租车轨迹数据挖掘进展[J]. 测绘通报, 2018(1):1-7. Mou N X, Xu Y J, Zhang H C, et al. A review of the mobile trajectory clustering methods[J]. Bulletin of Surveying and Mapping, 2018(1):1-7. (in Chinese)
[5] Grossi R, Marion A, Moghtasedi S. Finding structurally and temporally similar trajectories in graphs[C]//The 18th International Symposium on Experimental Algorithms, 2020, 160:1-13
[6] Ta N, Li G, Xie Y, et al. Signature-based trajectory similarity join[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(4):870-883.
[7] Shang S, Chen L, Wei Z, et al. Parallel trajectory similarity joins in spatial networks[J]. The VLDB Journal, 2018, 27(3):395-420.
[8] Qi S, Bouros P, Sacharidis D, et al. Efficient point-based trajectory search[C]//International Symposium on Spatial and Temporal Databases. Cham:Springer, 2015:179-196.
[9] Shang S, Chen L, Wei Z, et al. Trajectory similarity join in spatial networks[J]. Proceedings of the VLDB Endowment, 2017, 10(11):1178-1189.
[10] Ranu S, Deepak P, Telang A D, et al. Indexing and matching trajectories under inconsistent sampling rates[C]//2015 IEEE 31st International Conference on Data Engineering, 2015:999-1010.
[11] Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexing multi-dimensional timeseries with support for multiple distance measures[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:216-225.
[12] Guttman A. R-trees:a dynamic index structure for spatial searching[C]//Proceedings of 1984 ACM SIGMOD International Conference on Management of Data, 1984:47-57.
[13] Su H, Liu S, Zheng B, et al. A survey of trajectory distance measures and performance evaluation[J]. The VLDB Journal, 2020, 29(1):3-32.
[14] Xia Y, Wang G Y, Zhang X, et al. Spatio-temporal similarity measure for network constrained trajectory data[J]. International Journal of Computational Intelligence Systems, 2011, 4(5):1070-1079.
[15] Ding X, Yuan Y, Su L, et al. Modeling and optimization of image mapper for snapshot image mapping spectrometer[J]. IEEE Access, 2018, 6:29344-29352.
[16] Wang S, Bao Z, Culpepper J S, et al. Answering top-k exemplar trajectory queries[C]//2017 IEEE 33rd International Conference on Data Engineering, 2017:597-608.
[17] Frentaos E, Gratsias K, Theodoridis Y. Index-based most similar trajectory search[C]//2007 IEEE 23rd International Conference on Data Engineering, 2007:816-825.
[18] Driemel A, Mutzel P, Oettershagen L. Spatio-temporal top-k similarity search for trajectories in graphs[J/OL]. arXiv preprint, arXiv:2009.06778. (2020-10-19)[2022-08-05]. https://doi.org/10.48550/arXiv.2009.06778.
[19] Zhao P, Rao W, Zhang C, et al. SST:synchronized spatial-temporal trajectory similarity search[J]. GeoInformatica, 2020, 24(4):777-800.
[20] 王培, 江南, 万幼, 等. 应用Hausdorff距离的时空轨迹相似性度量方法[J]. 计算机辅助设计与图形学学报, 2019, 31(4):647-658. Wang P, Jiang N, Wan Y, et al. Measuring similarity of spatio-temporal trajectory using hausdorff distance[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(4):647-658. (in Chinese)
[21] 周星星, 吉根林, 张书亮. 时空轨迹相似性度量方法综述[J]. 地理信息世界, 2018, 25(4):11-18. Zhou X X, Ji G L, Zhang S L. Overview of the similarity measurement methods for spatialtemporal trajectory[J]. Geomatics World, 2018, 25(4):11-18. (in Chinese)
[22] Lemire D, Boytsov L. Decoding billions of integers per second through vectorization[J]. Software:Practice and Experience, 2015, 45(1):1-29.
[23] Mcauley J J, Leskovec J. Learning to discover social circles in ego networks[C]//The 26th Annual Conference on Neural Information Processing Systems, 2012:548-56.
[24] Yuan J, Zheng Y, Zhang C, et al. T-drive:driving directions based on taxi trajectories[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010:99-108.
[25] Kaggle. Taxi service trajectory prediction challenge 2015[EB/OL]. (2015-09-07)[2022-07-30]. https://www.kaggle.com/competitions/pkdd-15-predict-taxi-service-trajectory-i/data.
[26] U.S. Coast Guard. vessel traffic data[EB/OL]. (2015-01-01)[2022-07-30]. http://www.marinecadastre.gov/ais/.