More Web Proxy on the site http://driver.im/

research-article

Trajectory Similarity Measurement: An Efficiency Perspective

Authors:

Yanchuan Chang,

Christian S. Jensen,

Jianzhong QiAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 17, Issue 9

Pages 2293 - 2306

https://doi.org/10.14778/3665844.3665858

Published: 06 August 2024 Publication History

Abstract

Trajectories that capture object movement have numerous applications, in which similarity computation between trajectories often plays a key role. Traditionally, trajectory similarity is quantified by means of non-learned measures, e.g., Hausdorff, that operate directly on the trajectories. Recent studies exploit deep learning to map trajectories to d-dimensional vectors, called embeddings. Then, some distance measure, e.g., Manhattan, is applied to the embeddings to quantify trajectory similarity. The resulting similarities are inaccurate: they only approximate the similarities obtained using the non-learned measures. As embedding distance computation is efficient, focus has been on obtaining embeddings of high accuracy.

Adopting an efficiency perspective, we analyze the time complexities of both the non-learned and the learning-based approaches, finding that the time complexities of the former approaches are not necessarily higher. Through extensive experiments on open datasets, we find that only a few learning-based approaches can deliver the promised higher efficiency, when the embeddings can be pre-computed, while non-learned approaches are more efficient for one-off computations. Among the learning-based approaches, the self-attention-based ones are the fastest and the most accurate. These results have implications for the use of trajectory similarity approaches given different application requirements.

References

[1]

2013. OpenStreetMap Planet. https://wiki.openstreetmap.org/wiki/Planet.gpx.

[2]

2015. Porto Taxi Trajectory Dataset. https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i.

[3]

2018. DiDi GAIA Open Dataset. https://outreach.didichuxing.com/.

[4]

2020. Trajectory Distance Library. https://github.com/bguillouet/traj-dist.

[5]

2024. Technical Report. https://github.com/changyanchuan/TrajSimiMeasures/blob/master/paper_technical_report.pdf.

[6]

Rakesh Agrawal, Christos Faloutsos, and Arun Swami. 1993. Efficient Similarity Search in Sequence Databases. In International Conference on Foundations of Data Organization and Algorithms. 69--84.

[7]

Helmut Alt. 2009. The Computational Geometry of Comparing Shapes. In Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 235--248.

[8]

Helmut Alt and Michael Godau. 1995. Computing the Fréchet Distance between Two Polygonal Curves. International Journal of Computational Geometry & Applications 5, 01n02 (1995), 75--91.

[9]

Petko Bakalov, Marios Hadjieleftheriou, Eamonn Keogh, and Vassilis J Tsotras. 2005. Efficient Trajectory Joins using Symbolic Representations. In MDM. 86--93.

[10]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD. 322--331.

[11]

Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18, 9 (1975), 509--517.

Digital Library

[12]

Hanlin Cao, Haina Tang, Yulei Wu, Fei Wang, and Yongjun Xu. 2021. On Accurate Computation of Trajectory Similarity via Single Image Super-resolution. In IJCNN. 1--9.

[13]

Yanchuan Chang, Jianzhong Qi, Yuxuan Liang, and Egemen Tanin. 2023. Contrastive Trajectory Similarity Learning with Dual-Feature Attention. In ICDE. 2933--2945.

[14]

Yanchuan Chang, Jianzhong Qi, Egemen Tanin, Xingjun Ma, and Hanan Samet. 2021. Sub-Trajectory Similarity Join with Obfuscation. In SSDBM. 181--192.

[15]

Yanchuan Chang, Egemen Tanin, Xin Cao, and Jianzhong Qi. 2023. Spatial Structure-Aware Road Network Embedding via Graph Contrastive Learning. In EDBT. 144--156.

[16]

Chao Chen, Chengwu Liao, Xuefeng Xie, Yasha Wang, and Junfeng Zhao. 2019. Trip2Vec: A Deep Embedding Approach for Clustering and Profiling Taxi Trip Purposes. Personal and Ubiquitous Computing 23 (2019), 53--66.

Digital Library

[17]

Lu Chen, Yunjun Gao, Ziquan Fang, Xiaoye Miao, Christian S. Jensen, and Chenjuan Guo. 2019. Real-time Distributed Co-movement Pattern Detection on Streaming Trajectories. PVLDB 12, 10 (2019), 1208--1220.

Digital Library

[18]

Lei Chen and Raymond Ng. 2004. On the Marriage of LP-norms and Edit Distance. In PVLDB. 792--803.

[19]

Lei Chen, M Tamer Özsu, and Vincent Oria. 2005. Robust and Fast Similarity Search for Moving Object Trajectories. In SIGMOD. 491--502.

[20]

Yuanyi Chen, Peng Yu, Wenwang Chen, Zengwei Zheng, and Minyi Guo. 2021. Embedding-based Similarity Computation for Massive Vehicle Trajectory Data. IEEE Internet of Things Journal 9, 6 (2021), 4650--4660.

[21]

Ziwen Chen, Ke Li, Silin Zhou, Lisi Chen, and Shuo Shang. 2023. Towards Robust Trajectory Similarity Computation: Representation-based Spatio-temporal Similarity Quantification. World Wide Web 26 (2023), 1271--1294.

Digital Library

[22]

Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. 2014. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling. In NIPS Workshop on Deep Learning.

[23]

Ticiana L Coelho Da Silva, Karine Zeitouni, and José AF de Macêdo. 2016. Online Clustering of Trajectory Data Stream. In MDM. 112--121.

[24]

Liwei Deng, Yan Zhao, Zidan Fu, Hao Sun, Shuncheng Liu, and Kai Zheng. 2022. Efficient Trajectory Similarity Computation with Contrastive Learning. In CIKM. 365--374.

[25]

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL. 4171--4186.

[26]

Anne Driemel, Sariel Har-Peled, and Carola Wenk. 2010. Approximating the Fréchet Distance for Realistic Curves in Near Linear Time. In SoCG. 365--374.

[27]

Thomas Eiter and Heikki Mannila. 1994. Computing Discrete Fréchet Distance. Technical Report. Technical University of Vienna.

[28]

Ziquan Fang, Yuntao Du, Lu Chen, Yujia Hu, Yunjun Gao, and Gang Chen. 2021. E2DTC: An End to End Deep Trajectory Clustering Framework via Self-training. In ICDE. 696--707.

[29]

Ziquan Fang, Yuntao Du, Xinjun Zhu, Lu Chen, Yunjun Gao, and Christian S. Jensen. 2022. Spatio-temporal Trajectory Similarity Learning in Road Networks. In KDD. 347--356.

[30]

Tao-Yang Fu and Wang-Chien Lee. 2020. Trembr: Exploring Road Networks for Trajectory Representation Learning. ACM Transactions on Intelligent Systems and Technology 11, 1 (2020), 10:1--25.

Digital Library

[31]

Maxime Gariel, Ashok N Srivastava, and Eric Feron. 2011. Trajectory Clustering and an Application to Airspace Monitoring. IEEE Transactions on Intelligent Transportation Systems 12, 4 (2011), 1511--1524.

Digital Library

[32]

Antonin Guttman. 1984. R-trees:ADynamic Index Structure for Spatial Searching. In SIGMOD. 47--57.

[33]

Peng Han, Jin Wang, Di Yao, Shuo Shang, and Xiangliang Zhang. 2021. A Graph-based Approach for Trajectory Similarity Computation in Spatial Networks. In KDD. 556--564.

[34]

Huajun He, Ruiyuan Li, Sijie Ruan, Tianfu He, Jie Bao, Tianrui Li, and Yu Zheng. 2022. TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores. In ICDE. 2306--2318.

[35]

Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Computation 9, 8 (1997), 1735--1780.

Digital Library

[36]

Yu Jiang, Guoliang Li, Jianhua Feng, and Wen-Syan Li. 2014. String Similarity Joins: An Experimental Evaluation. PVLDB 7, 8 (2014), 625--636.

Digital Library

[37]

Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535--547.

[38]

Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005. Exact Indexing of Dynamic Time Warping. Knowledge and Information Systems 7, 3 (2005), 358--386.

Digital Library

[39]

Satoshi Koide, Chuan Xiao, and Yoshiharu Ishikawa. 2020. Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints. PVLDB 13, 12 (2020), 2188--2201.

Digital Library

[40]

Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. 2007. Trajectory Clustering: A Partition-and-group Framework. In SIGMOD. 593--604.

Digital Library

[41]

Seok-Lyong Lee, Seok-Ju Chun, Deok-Hwan Kim, Ju-Hong Lee, and Chin-Wan Chung. 2000. Similarity Search for Multidimensional Data Sequences. In ICDE. 599--608.

[42]

Xiaohui Li, Vaida Ceikute, Christian S. Jensen, and Kian-Lee Tan. 2012. Effective Online Group Discovery in Trajectory Databases. IEEE Transactions on Knowledge and Data Engineering 25, 12 (2012), 2752--2766.

Digital Library

[43]

Xiucheng Li, Kaiqi Zhao, Gao Cong, Christian S. Jensen, and Wei Wei. 2018. Deep Representation Learning for Trajectory Similarity Computation. In ICDE. 617--628.

[44]

Bin Lin and Jianwen Su. 2008. One Way Distance: For Shape based Similarity Search of Moving Object Trajectories. GeoInformatica 12 (2008), 117--142.

Digital Library

[45]

Jessica Lin, Eamonn Keogh, Stefano Lonardi, and Bill Chiu. 2003. A Symbolic Representation of Time Series, with Implications for Streaming Algorithms. In SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 2--11.

Digital Library

[46]

An Liu, Yifan Zhang, Xiangliang Zhang, Guanfeng Liu, Yanan Zhang, Zhixu Li, Lei Zhao, Qing Li, and Xiaofang Zhou. 2022. Representation Learning with Multi-level Attention for Activity Trajectory Similarity Computation. IEEE Transactions on Knowledge and Data Engineering 34, 5 (2022), 2387--2400.

[47]

Xiang Liu, Xiaoying Tan, Yuchun Guo, Yishuai Chen, and Zhe Zhang. 2022. CSTRM: Contrastive Self-Supervised Trajectory Representation Model for Trajectory Similarity Computation. Computer Communications 185 (2022), 159--167.

Digital Library

[48]

Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2018), 824--836.

Digital Library

[49]

Pierre-François Marteau. 2008. Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 2 (2008), 306--318.

Digital Library

[50]

Michael D Morse and Jignesh M Patel. 2007. An Efficient and Accurate Method for Evaluating Time Series Similarity. In SIGMOD. 569--580.

[51]

Xavier Olive, Luis Basora, Benoit Viry, and Richard Alligier. 2020. Deep Trajectory Clustering with Autoencoders. In International Conference for Research in Air Transportation.

[52]

Hae-Sang Park and Chi-Hyuck Jun. 2009. A Simple and Fast Algorithm for K-medoids Clustering. Expert Systems with Applications 36, 2 (2009), 3336--3341.

Digital Library

[53]

Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving Language Understanding by Generative Pre-Training. OpenAI (2018).

[54]

Sayan Ranu, Padmanabhan Deepak, Aditya D. Telang, Prasad Deshpande, and Sriram Raghavan. 2015. Indexing and Matching Trajectories under Inconsistent Sampling Rates. In ICDE. 999--1010.

[55]

Hanan Samet. 1984. The Quadtree and Related Hierarchical Data Structures. Comput. Surveys 16, 2 (1984), 187--260.

Digital Library

[56]

Shuo Shang, Lisi Chen, Zhewei Wei, Christian S. Jensen, Kai Zheng, and Panos Kalnis. 2017. Trajectory Similarity Join in Spatial Networks. PVLDB 10, 11 (2017), 1178--1189.

Digital Library

[57]

Zeyuan Shang, Guoliang Li, and Zhifeng Bao. 2018. DITA: Distributed In-memory Trajectory Analytics. In SIGMOD. 725--740.

[58]

Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. 2020. A Survey of Trajectory Distance Measures and Performance Evaluation. The VLDB Journal 29 (2020), 3--32.

Digital Library

[59]

Yaguang Tao, Alan Both, Rodrigo I. Silveira, Kevin Buchin, Stef Sijben, Ross S. Purves, Patrick Laube, Dongliang Peng, Kevin Toohey, and Matt Duckham. 2021. A Comparative Analysis of Trajectory Similarity Measures. GIScience & Remote Sensing 58, 5 (2021), 643--669.

[60]

David Alexander Tedjopurnomo, Xiucheng Li, Zhifeng Bao, Gao Cong, Farhana Choudhury, and A. Kai Qin. 2021. Similar Trajectory Search with Spatio-temporal Deep Representation Learning. ACM Transactions on Intelligent Systems and Technology 12, 6 (2021), 77:1--26.

Digital Library

[61]

Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. LLaMA: Open and Efficient Foundation Language Models. arXiv preprint arXiv:2302.13971 (2023).

[62]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention Is All You Need. In NIPS. 6000--6010.

[63]

Michail Vlachos, Marios Hadjieleftheriou, Dimitrios Gunopulos, and Eamonn Keogh. 2003. Indexing Multi-Dimensional Time-Series with Support for Multiple Distance Measures. In KDD. 216--225.

[64]

Michail Vlachos, George Kollios, and Dimitrios Gunopulos. 2002. Discovering Similar Multidimensional Trajectories. In ICDE. 673--684.

[65]

Sheng Wang, Zhifeng Bao, J. Shane Culpepper, and Gao Cong. 2021. A Survey on Trajectory Data Management, Analytics, and Learning. Comput. Surveys 54, 2 (2021), 39:1--36.

[66]

Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Zizhe Xie, Qizhi Liu, and Xiaolin Qin. 2018. Torch: A Search Engine for Trajectory Data. In SIGIR. 535--544.

Digital Library

[67]

Tingting Wang, Shixun Huang, Zhifeng Bao, J. Shane Culpepper, and Reza Arablouei. 2022. Representative Routes Discovery from Massive Trajectories. In KDD. 4059--4069.

[68]

Taizheng Wang, Chunyang Ye, Hui Zhou, Mingwang Ou, and Bo Cheng. 2021. AIS Ship Trajectory Clustering based on Convolutional Auto-encoder. In Intelligent Systems and Applications. 529--546.

[69]

Zheng Wang, Cheng Long, and Gao Cong. 2023. Similar Sports Play Retrieval with Deep Reinforcement Learning. IEEE Transactions on Knowledge and Data Engineering 35, 4 (2023), 4253--4266.

Digital Library

[70]

Zheng Wang, Cheng Long, Gao Cong, and Ce Ju. 2019. Effective and Efficient Sports Play Retrieval with Deep Representation Learning. In KDD. 499--509.

[71]

Phillip GD Ward, Zhen He, Rui Zhang, and Jianzhong Qi. 2014. Real-time Continuous Intersection Joins Over Large Sets of Moving Objects Using Graphic Processing Units. VLDBJ 23 (2014), 965--985.

Digital Library

[72]

Limin Xiao, Yao Zheng, Wenqi Tang, Guangchao Yao, and Li Ruan. 2013. Parallelizing Dynamic Time Warping Algorithm Using Prefix Computations on GPU. In IEEE International Conference on High Performance Computing and Communications & IEEE International Conference on Embedded and Ubiquitous Computing. 294--299.

[73]

Dong Xie, Feifei Li, and Jeff M. Phillips. 2017. Distributed Trajectory Similarity Search. PVLDB 10, 11 (2017), 1478--1489.

Digital Library

[74]

Kiyoung Yang and Cyrus Shahabi. 2004. A PCA-based Similarity Measure for Multivariate Time Series. In ACM International Workshop on Multimedia Databases. 65--74.

Digital Library

[75]

Peilun Yang, Hanchen Wang, Defu Lian, Ying Zhang, Lu Qin, and Wenjie Zhang. 2022. TMN: Trajectory Matching Networks for Predicting Similarity. In ICDE. 1700--1713.

[76]

Peilun Yang, Hanchen Wang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2021. T3S: Effective Representation Learning for Trajectory Similarity Computation. In ICDE. 2183--2188.

[77]

Sean Bin Yang, Jilin Hu, Chenjuan Guo, Bin Yang, and Christian S. Jensen. 2023. LightPath: Lightweight and Scalable Path Representation Learning. In KDD. 2999--3010.

[78]

Di Yao, Gao Cong, Chao Zhang, and Jingping Bi. 2019. Computing Trajectory Similarity in Linear Time: A Generic Seed-guided Neural Netric learning approach. In ICDE. 1358--1369.

[79]

Di Yao, Haonan Hu, Lun Du, Gao Cong, Shi Han, and Jingping Bi. 2022. Traj-GAT: A Graph-based Long-term Dependency Modeling Approach for Trajectory Similarity Computation. In KDD. 2275--2285.

[80]

Di Yao, Chao Zhang, Zhihua Zhu, Jianhui Huang, and Jingping Bi. 2017. Trajectory Clustering via Deep Representation Learning. In IJCNN. 3880--3887.

[81]

Rex Ying, Jiangwei Pan, Kyle Fox, and Pankaj K. Agarwal. 2016. A Simple Efficient Approximation Algorithm for Dynamic Time Warping. In SIGSPATIAL. 21:1--10.

[82]

Haitao Yuan and Guoliang Li. 2019. Distributed In-memory Trajectory Similarity Search and Join on Road Network. In ICDE. 1262--1273.

[83]

Mingxuan Yue, Yaguang Li, Haoze Yang, Ritesh Ahuja, Yao-Yi Chiang, and Cyrus Shahabi. 2019. DETECT: Deep Trajectory Clustering for Mobility-behavior Analysis. In IEEE International Conference on Big Data. 988--997.

[84]

Hanyuan Zhang, Xingyu Zhang, Qize Jiang, Baihua Zheng, Zhenbang Sun, Weiwei Sun, and Changhu Wang. 2020. Trajectory Similarity Learning with Auxiliary Supervision and Optimal Matching. In IJCAI. 11--17.

[85]

Bolong Zheng, Lianggui Weng, Xi Zhao, Kai Zeng, Xiaofang Zhou, and Christian S. Jensen. 2021. REPOSE: Distributed Top-k Trajectory Similarity Search with Local Reference Point Tries. In ICDE. 708--719.

[86]

Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. Geolife: A Collaborative Social Networking Service among User, Location and Trajectory. IEEE Data Engineering Bulletin 33, 2 (2010), 32--39.

[87]

Silin Zhou, Jing Li, Hao Wang, Shuo Shang, and Peng Han. 2023. GRLSTM: Trajectory Similarity Computation with Graph-based Residual LSTM. In AAAI. 4972--4980.

Cited By

Wang YCai JYang HWang JLiang BZhao X(2024)A New Composite Dissimilarity Measure for Planar Curves Based on Higher-Order DerivativesMathematics10.3390/math1219308312:19(3083)Online publication date: 1-Oct-2024
https://doi.org/10.3390/math12193083
Hu ZHe YShen YJo MCollotta MShen GKong X(2024)Vehicular Social Dynamic Anomaly Detection With Recurrent Multi-Mask Aggregator Enabled VAEIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.345756925:12(21709-21722)Online publication date: Dec-2024
https://doi.org/10.1109/TITS.2024.3457569

Recommendations

Trajectory similarity clustering based on multi-feature distance measurement

With the development of GPS-enabled devices, wireless communication and storage technologies, trajectories representing the mobility of moving objects are accumulated at an unprecedented pace. They contain a large amount of temporal and spatial semantic ...
Trajectory similarity measures

Storing, querying, and analyzing trajectories is becoming increasingly important, as the availability and volumes of trajectory data increases. One important class of trajectory analysis is computing trajectory similarity. This paper introduces and ...
SST: Synchronized Spatial-Temporal Trajectory Similarity Search
Abstract
The volume of trajectory data has become tremendously large in recent years. How to effectively and efficiently search similar trajectories has become an important task. Firstly, to measure the similarity between a trajectory and a query, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 17, Issue 9

May 2024

282 pages

Editors:
Meihui Zhang
Beijing Institute of Technology
,
Cyrus Shahabi
University of Southern California

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 06 August 2024

Published in PVLDB Volume 17, Issue 9

Check for updates

Badges

Artifacts Available / v1.1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
98
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)7

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang YCai JYang HWang JLiang BZhao X(2024)A New Composite Dissimilarity Measure for Planar Curves Based on Higher-Order DerivativesMathematics10.3390/math1219308312:19(3083)Online publication date: 1-Oct-2024
https://doi.org/10.3390/math12193083
Hu ZHe YShen YJo MCollotta MShen GKong X(2024)Vehicular Social Dynamic Anomaly Detection With Recurrent Multi-Mask Aggregator Enabled VAEIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.345756925:12(21709-21722)Online publication date: Dec-2024
https://doi.org/10.1109/TITS.2024.3457569

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents