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.
[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/.
