基于深度学习的轨迹相似性度量方法研究综述

doi:10.3778/j.issn.1673-9418.2404006

摘要/Abstract

摘要： 移动通信和传感设备技术的发展与应用，产生了大量轨迹数据，这些数据呈现出高维异构性、多粒度性和不确定性等特征，这使得传统基于点对匹配的轨迹相似性度量方法难以适用。近年来，研究者将深度学习技术用于轨迹相似性度量，旨在挖掘更多轨迹特征，提高计算效率，增强模型鲁棒性。对近年来基于深度学习的轨迹相似性度量方法进行系统性综述。阐述轨迹的相关定义；根据相似性度量方法分类框架，从度量表示形式（即序列表示与图表示）和学习策略（即表示学习、度量学习与对比学习）两个角度综述相关方法。从轨迹数据预处理、嵌入表示学习和相似性度量三个方面，对上述方法的实现原理及其特点进行详细对比分析；阐述了基于深度学习的轨迹相似性度量方法的常用数据集和评估指标，并对学习模型的来源、评估指标、时间复杂度和应用场景进行了归纳总结。分析了当前轨迹相似性度量方法所面临的挑战并对未来研究方向进行了展望。

关键词: 轨迹相似性度量, 深度学习, 度量表示形式, 学习策略

Abstract: The development and application of mobile communication and sensing device technology have generated a large amount of trajectory data, which presents characteristics such as high-dimensional heterogeneity, multi-granularity, and uncertainty, which makes traditional trajectory similarity measurement methods based on point pair matching difficult to apply. In recent years, deep learning techniques have been applied to measuring trajectory similarity, aiming to mine more trajectory features, improve computational efficiency, and enhance model robustness. This paper systematically reviews recent trajectory similarity measurement methods based on deep learning. Firstly, it explains the relevant definitions of trajectories. Then, it provides an overview of these methods from two perspectives: metric representation forms (i.e. sequence representation and graph representation) and learning strategies (i.e. representation learning, metric learning, and contrastive learning). Furthermore, it conducts a detailed and comparative analysis on the implementation principles and characteristics of these methods from three aspects: trajectory data preprocessing, embedding representation learning, and similarity measurement. Afterwards, the commonly used datasets and evaluation metrics for trajectory similarity measurement methods based on deep learning are analyzed, and the sources, evaluation metrics, time complexity, and application scenarios of the learning model are summarized. Finally, it analyzes the challenges faced by trajectory similarity measurement methods and prospects future research directions.

Key words: trajectory similarity measurement, deep learning, metric representation form, learning strategy

孟祥福, 师光启, 张霄雁, 冷强奎, 方金凤. 基于深度学习的轨迹相似性度量方法研究综述[J]. 计算机科学与探索, 2025, 19(3): 623-644.

MENG Xiangfu, SHI Guangqi, ZHANG Xiaoyan, LENG Qiangkui, FANG Jinfeng. Survey on Deep Learning Based Trajectory Similarity Measurement Approaches[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(3): 623-644.

参考文献

[1] 安敬民, 李冠宇, 蒋伟, 等. 基于用户活动轨迹和个性化区域划分的兴趣点推荐[J]. 计算机学报, 2022, 45(6): 1176-1194.
AN J M, LI G Y, JIANG W, et al. A point-of-interest recommendation method based on activity tracks and personalized-area partitions of users[J]. Chinese Journal of Computers, 2022, 45(6): 1176-1194.
[2] 孟祥福, 许睿航. 基于动态时空神经网络的城市交通流量预测方法[J]. 计算机科学, 2023, 50(S1): 602-608.
MENG X F, XU R H. Urban traffic flow forecasting method based on dynamic spatio-temporal neural network[J]. Computer Science, 2023, 50(S1): 602-608.
[3] LI Z H, HAN J W, JI M, et al. MoveMine[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(4): 1-32.
[4] RESHEFF Y S. Online trajectory segmentation and summary with applications to visualization and retrieval[C]//Proceedings of the 2016 IEEE International Conference on Big Data. Piscataway: IEEE, 2016: 1832-1840.
[5] FANG Z Q, DU Y T, CHEN L, et al. E2DTC: an end to end deep trajectory clustering framework via self-training[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway: IEEE, 2021: 696-707.
[6] MA Y X, ZHU X G, ZHANG S B, et al. TrafficPredict: trajectory prediction for heterogeneous traffic-agents[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 6120-6127.
[7] DJENOURI Y, DJENOURI D, LIN J C. Trajectory outlier detection: new problems and solutions for smart cities[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(2): 1-28.
[8] YI B K, JAGADISH H V, FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]//Proceedings of the 14th International Conference on Data Engineering. Piscataway: IEEE, 1998: 201-208.
[9] CHEN L, ÖZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 491-502.
[10] ALT H. The computational geometry of comparing shapes[C]//Efficient Algorithms. Berlin, Heidelberg: Springer, 2009: 235-248.
[11] EITER T, MANNILA H. Computing discrete Fréchet distance: CD-TR 94/64[R]. Technical University of Vienna.Christian Doppler Labor für Expertensysteme, 1994.
[12] CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 30th International Conference on Very Large Data Bases-Volume 30. San Francisco: Morgan Kaufmann, 2004: 792-803.
[13] SU H, LIU S C, ZHENG B L, et al. A survey of trajectory distance measures and performance evaluation[J]. The VLDB Journal, 2020, 29(1): 3-32.
[14] HU D L, CHEN L, FANG H X, et al. Spatio-temporal trajectory similarity measures: a comprehensive survey and quantitative study[EB/OL]. [2024-01-15]. https://arxiv.org/abs/2303.05012.
[15] GRAVES A, MOHAMED A R, HINTON G. Speech recognition with deep recurrent neural networks[C]//Proceedings of the 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway: IEEE, 2013: 6645-6649.
[16] VASWANI A, SHAZEER N, PARMAR N, et al.Attention is all you need[C]//Advances in Neural Information Processing Systems 30, Long Beach, Dec 4-9, 2017: 5998-6008.
[17] LI X C, ZHAO K Q, CONG G, et al. Deep representation learning for trajectory similarity computation[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering. Piscataway: IEEE, 2018: 617-628.
[18] CHEN Z W, LI K, ZHOU S L, et al. Towards robust trajectory similarity computation: representation-based spatio-temporal similarity quantification[J]. World Wide Web, 2023, 26(4): 1271-1294.
[19] ZHANG Y F, LIU A, LIU G F, et al. Deep representation learning of activity trajectory similarity computation[C]//Proceedings of the 2019 IEEE International Conference on Web Services. Piscataway: IEEE, 2019: 312-319.
[20] LIU A, ZHANG Y F, ZHANG X L, et al. Representation learning with multi-level attention for activity trajectory similarity computation[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(5): 2387-2400.
[21] MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space[EB/OL]. [2024-01-15]. https://arxiv.org/abs/1301.3781.
[22] PENNINGTON J, SOCHER R, MANNING C D. GloVe: global vectors for word representation[C]//Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. Stroudsburg: ACL, 2014: 1532-1543.
[23] SUTSKEVER I, VINYALS O, LE Q V, et al. Sequence to sequence learning with neural networks[C]//Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2, 2014: 3104-3112.
[24] CHO K, VAN MERRIENBOER B, GULCEHRE C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[EB/OL]. [2024-01-15]. https://arxiv.org/abs/1406.1078.
[25] HOCHREITER S, SCHMIDHUBER J. Long short-term me-mory[J]. Neural Computation, 1997, 9(8): 1735-1780.
[26] PANDIT S, GUPTA S. A comparative study on distance measuring approaches for clustering[J]. International Journal of Research in Computer Science, 2011, 2(1): 29-31.
[27] KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Locally adaptive dimensionality reduction for indexing large time series databases[C]//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2001: 151-162.
[28] GONG X D, XIONG Y, HUANG W C, et al. Fast similarity search of multi-dimensional time series via segment rotation[M]//Database systems for advanced applications. Cham: Springer, 2015: 108-124.
[29] GOWANLOCK M, CASANOVA H. Distance threshold similarity searches: efficient trajectory indexing on the GPU[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(9): 2533-2545.
[30] XIE D, LI F F, PHILLIPS J M. Distributed trajectory similarity search[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1478-1489.
[31] YAO D, ZHANG C, ZHU Z H, et al. Trajectory clustering via deep representation learning[C]//Proceedings of the 2017 International Joint Conference on Neural Networks. Piscataway: IEEE, 2017: 3880-3887.
[32] 龚玺, 裴韬, 孙嘉, 等. 时空轨迹聚类方法研究进展[J]. 地理科学进展, 2011, 30(5): 522-534.
GONG X, PEI T, SUN J, et al. Review of the research progresses in trajectory clustering methods[J]. Progress in Geography, 2011, 30(5): 522-534.
[33] PICIARELLI C, FORESTI G L. On-line trajectory clustering for anomalous events detection[J]. Pattern Recognition Letters, 2006, 27(15): 1835-1842.
[34] 刘良旭, 乐嘉锦, 乔少杰, 等. 基于轨迹点局部异常度的异常点检测算法[J]. 计算机学报, 2011, 34(10): 1966-1975.
LIU L X, LE J J, QIAO S J, et al. Trajectory outliers detection based on local outlying degree[J]. Chinese Journal of Computers, 2011, 34(10): 1966-1975.
[35] DRIEMEL A, SILVESTRI F. Locality-sensitive hashing of curves[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1703.04040.
[36] YAO D, CONG G, ZHANG C, et al. Computing trajectory similarity in linear time: a generic seed-guided neural metric learning approach[C]//Proceedings of the 2019 IEEE 35th International Conference on Data Engineering. Piscataway: IEEE, 2019: 1358-1369.
[37] ZHANG H Y, ZHANG X Y, JIANG Q Z, et al. Trajectory similarity learning with auxiliary supervision and optimal matching[C]//Proceedings of the 29th International Joint Conference on Artificial Intelligence, 2021: 3209-3215.
[38] CHEN Y Y, YU P, CHEN W W, et al. Embedding-based similarity computation for massive vehicle trajectory data[J]. IEEE Internet of Things Journal, 2022, 9(6): 4650-4660.
[39] YANG P L, WANG H C, ZHANG Y, et al. T3S: effective representation learning for trajectory similarity computation[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway: IEEE, 2021: 2183-2188.
[40] YANG P L, WANG H C, LIAN D F, et al. TMN: trajectory matching networks for predicting similarity[C]//Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Piscataway: IEEE, 2022: 1700-1713.
[41] FAGHRI F, FLEET D J, KIROS J R, et al. VSE++: improving visual-semantic embeddings with hard negatives[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1707.05612.
[42] BROMLEY J, GUYON I, LECUN Y, et al. Signature verification using a “siamese” time delay neural network[C]// Advances in Neural Information Processing Systems 6. San Francisco: Morgan Kaufmann, 1994: 737-744.
[43] LIU X, TAN X Y, GUO Y C, et al. CSTRM: contrastive self-supervised trajectory representation model for trajectory similarity computation[J]. Computer Communications, 2022, 185: 159-167.
[44] DENG L W, ZHAO Y, FU Z D, et al. Efficient trajectory similarity computation with contrastive learning[C]//Proceedings of the 31st ACM International Conference on Information and Knowledge Management. New York: ACM, 2022: 365-374.
[45] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 2, 2013: 3111-3119.
[46] DEVLIN J, CHANG M W, LEE K, et al. BERT: pre-training of deep bidirectional transformers for language understanding[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1810.04805.
[47] KRIZHEVSKY A, SUTSKEVER I, HINTON G E. ImageNet classification with deep convolutional neural networks[J]. Communications of the ACM, 2017, 60(6): 84-90.
[48] SZEGEDY C, LIU W, JIA Y, et al. Going deeper with convolutions[C]//Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2015: 1-9.
[49] HE K, ZHANG X, REN S, et al. Deep residual learning for image recognition[C]//Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2016: 770-778.
[50] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.
[51] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1609.02907.
[52] VELIČKOVIĆ P, CUCURULL G, CASANOVA A, et al. Graph attention networks[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1710.10903.
[53] LI S C, LIANG M H, LIU R W. Vessel trajectory similarity measure based on deep convolutional autoencoder[C]//Proceedings of the 2020 5th IEEE International Conference on Big Data Analytics. Piscataway: IEEE, 2020: 333-338.
[54] LIANG M H, LIU R W, LI S C, et al. An unsupervised learning method with convolutional auto-encoder for vessel trajectory similarity computation[J]. Ocean Engineering, 2021, 225: 108803.
[55] CHANG X L, LIN S F, LIU X L, et al. TISM-CAE: a fast unsupervised learning method for trajectory similarity measure via convolutional auto-encoder[C]//Proceedings of the 7th International Conference on Cyber Security and Information Engineering. New York: ACM, 2022: 140-148.
[56] NISHIO M, NAGASHIMA C, HIRABAYASHI S, et al. Convolutional auto-encoder for image denoising of ultra-low-dose CT[J]. Heliyon, 2017, 3(8): e00393.
[57] CAO H L, TANG H N, WU Y L, et al. On accurate computation of trajectory similarity via single image super-resolution[C]//Proceedings of the 2021 International Joint Conference on Neural Networks. Piscataway: IEEE, 2021: 1-9.
[58] 曹亚媛. 数据驱动的白鹳行为模式挖掘[D]. 西安: 西安科技大学, 2021.
CAO Y Y. Data-driven behavior pattern mining of storks[D]. Xi􀆳an: Xi􀆳an University of Science and Technology, 2021.
[59] ZHAN R, SHAO Z P, PAN J C. Advance in character mining and prediction of ship behavior based on AIS data[J]. Journal of Geo-information Science, 2021, 23(12): 2111-2127.
[60] 冯琦森. 基于出租车轨迹的居民出行热点路径和区域挖掘[D]. 重庆: 重庆大学, 2016.
FENG Q S. Hot path and area mining of residents􀆳 travel based on taxi trajectory[D]. Chongqing: Chongqing University, 2016.
[61] 吴睿智. 轨迹数据挖掘关键技术研究[D]. 成都: 电子科技大学, 2020.
WU R Z. Research on key technologies of trajectory data mining[D]. Chengdu: University of Electronic Science and Technology of China, 2020.
[62] ZHANG R, RONG Y C, WU Z L, et al. Trajectory similarity assessment on road networks via embedding learning[C]//Proceedings of the 2020 IEEE 6th International Conference on Multimedia Big Data. Piscataway: IEEE, 2020: 1-8.
[63] HAN P, WANG J, YAO D, et al. A graph-based approach for trajectory similarity computation in spatial networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2021: 556-564.
[64] ZHOU S L, HAN P, YAO D, et al. Spatial-temporal fusion graph framework for trajectory similarity computation[J]. World Wide Web, 2023, 26(4): 1501-1523.
[65] ZHOU S L, LI J, WANG H, et al. GRLSTM: trajectory simi-larity computation with graph-based residual LSTM[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(4): 4972-4980.
[66] GROVER A, LESKOVEC J. node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 855-864.
[67] LEDIG C, THEIS L, HUSZAR F, et al. Photo-realistic-single image super-resolution using a generative adversarial network[C]//Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2017: 4681-4690.
[68] YAO D, HU H N, DU L, et al. TrajGAT[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2022: 2275-2285.
[69] FANG Z Q, DU Y T, ZHU X J, et al. Spatio-temporal trajectory similarity learning in road networks[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2022: 347-356.
[70] SAMET H. An overview of quadtrees, octrees, and related hierarchical data structures[M]//Theoretical foundations of computer graphics and CAD. Berlin, Heidelberg: Springer, 1988: 51-68.
[71] BENGIO Y, LOURADOUR J, COLLOBERT R, et al. Curriculum learning[C]//Proceedings of the 26th Annual International Conference on Machine Learning, 2009: 41-48.
[72] LUO S Z, ZENG W M, SUN B W. Contrastive learning for graph-based vessel trajectory similarity computation[J]. Journal of Marine Science and Engineering, 2023, 11(9): 1840.
[73] CHANG Y C, QI J Z, LIANG Y X, et al. Contrastive trajectory similarity learning with dual-feature attention[C]//Proceedings of the 2023 IEEE 39th International Conference on Data Engineering. Piscataway: IEEE, 2023: 2933-2945.
[74] MOREIRA-MATIAS L, GAMA J, FERREIRA M, et al. Time-evolving O-D matrix estimation using high-speed GPS data streams[J]. Expert Systems with Applications, 2016, 44: 275-288.
[75] YUAN J, ZHENG Y, ZHANG C Y, et al. T-drive: driving directions based on taxi trajectories[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108.
[76] WANG Y D, XU D W, PENG P, et al. Analysis of road travel behaviour based on big trajectory data[J]. IET Intelligent Transport Systems, 2020, 14(12): 1691-1703.
[77] LI H H, JIAO H, YANG Z L. AIS data-driven ship trajectory prediction modelling and analysis based on machine learning and deep learning methods[J]. Transportation Research Part E: Logistics and Transportation Review, 2023, 175: 103152.
[78] ZHENG Y, XIE X, MA W Y. GeoLife: a collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2009, 33: 32-39.
[79] BESSE P C, GUILLOUET B, LOUBES J M, et al. Review and perspective for distance-based clustering of vehicle trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(11): 3306-3317.
[80] RANU S, DEEPAK P, TELANG A D, et al. Indexing and matching trajectories under inconsistent sampling rates[C]//Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway: IEEE, 2015: 999-1010.
[81] ZHENG Q H, ZHAO P H, WANG H J, et al. Fine-grained modulation classification using multi-scale radio transformer with dual-channel representation[J]. IEEE Communications Letters, 2022, 26(6): 1298-1302.
[82] ZHENG Q H, ZHAO P H, ZHANG D L, et al. MR-DCAE: manifold regularization-based deep convolutional auto-encoder for unauthorized broadcasting identification[J]. International Journal of Intelligent Systems, 2021, 36(12): 7204-7238.
[83] DING J F, FANG J H, ZHANG Z L, et al. Real-time trajectory similarity processing using longest common subsequence[C]//Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems. Piscataway: IEEE, 2019: 1398-1405.
[84] BERGROTH L, HAKONEN H, RAITA T. A survey of longest common subsequence algorithms[C]//Proceedings of the 7th International Symposium on String Processing and Information Retrieval. Piscataway: IEEE, 2000: 39-48.
[85] PAN Z C, CHAO P F, FANG J H, et al. TraSP: a general framework for online trajectory similarity processing[C]//Proceedings of the 21st International Conference on Web Information Systems Engineering. Cham: Springer, 2020: 384-397.
[86] FU T Y, LEE W C. Trembr: exploring road networks for trajectory representation learning[J]. ACM Transactions on Intelligent Systems and Technology, 2020, 11(1): 1-25.
[87] GUO K, WANG D B, ZHI H, et al. Privacy-preserving trajectory generation algorithm considering utility based on semantic similarity awareness[C]//Proceedings of the 2022 IEEE International Conference on Communications. Piscataway: IEEE, 2022: 992-997.
[88] CAO H C, XU F L, SANKARANARAYANAN J, et al. Habit2vec: trajectory semantic embedding for living pattern recognition in population[J]. IEEE Transactions on Mobile Computing, 2020, 19(5): 1096-1108.

编辑推荐 0

Metrics

阅读次数

全文

107

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	30	0	77

	来源	本网站

	次数	107
	比例	100%

摘要

123

最新录用	在线预览	正式出版

63	0	59

	来源	本网站

	次数	123
	比例	100%