Abstract
In the tasks of location-based services and vehicle trajectory mining, trajectory similarity computation is the fundamental operation and affects both the efficiency and effectiveness of the downstream applications. Existing trajectory representation learning works either use grids to cluster trajectory points or require external information such as road network types, which is not good enough in terms of query accuracy and applicable scenarios. In this paper, we propose a novel partition-based representation learning framework PT2vec for similarity computation by exploiting the underlying road segments without extra information. To reduce the number of words and ensure that two spatially similar trajectories have embeddings closely located in the latent feature space, we partition the network into multiple sub-networks where each is represented by a word. Then we adopt the GRU-based seq2seq model for word embedding, and a loss function is designed based on spatial features and topological constraints to improve the accuracy of representation and speed up model training. Furthermore, a hierarchical tree index PT-Gtree is built to store trajectories for further improving query efficiency based on the proposed pruning strategy. Experiments show that our method is both more accurate and efficient than the state-of-the-art solutions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Challenge, T.S.T.P.: https://www.geolink.pt/ecmlpkdd2015-challenge/ (2015)
Chao, P., He, D., Li, L., Zhang, M., Zhou, X.: Efficient trajectory contact query processing. In: Jensen, C.S., et al. (eds.) DASFAA 2021. LNCS, vol. 12681, pp. 658–666. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-73194-6_44
Chao, P., Xu, Y., Hua, W., Zhou, X.: A survey on map-matching algorithms. In: Borovica-Gajic, R., Qi, J., Wang, W. (eds.) ADC 2020. LNCS, vol. 12008, pp. 121–133. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39469-1_10
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD, pp. 491–502 (2005)
Fu, T.Y., Lee, W.C.: Trembr: exploring road networks for trajectory representation learning. ACM TIST 11(1), 1–25 (2020)
Karypis, G., Kumar, V.: Analysis of multilevel graph partitioning. In: Conference on Supercomputing, pp. 29–29. IEEE (1995)
Li, L., Zheng, K., Wang, S., Hua, W., Zhou, X.: Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. VLDB J. 27(3), 321–345 (2018). https://doi.org/10.1007/s00778-018-0499-4
Li, F., Zhang, Q., Zhang, W.: Graph partitioning strategy for the topology design of industrial network. IET Commun. 1(6), 1104–1110 (2007)
Li, X., Zhao, K., et al., G.C.: Deep representation learning for trajectory similarity computation. In: Proceedings of the IEEE 34th ICDE, pp. 617–628 (2018)
Mao, Y., Zhong, H., Xiao, X., Li, X.: A segment-based trajectory similarity measure in the urban transportation systems. Sensors 17(3), 524 (2017)
Ranu, S., Deepak, P., Telang, A.D., et al.: Indexing and matching trajectories under inconsistent sampling rates. In: ICDE, pp. 999–1010. IEEE (2015)
Sheng, W., Zhifeng, B., Shane, C.J., Gao, C.: A survey on trajectory data management, analytics, and learning. CSUR 54(2), 1–36 (2021)
Sousa, R.S.D., Boukerche, A., Loureiro, A.A.: Vehicle trajectory similarity: models, methods, and applications. ACM Comput. Surv. (CSUR) 53(5), 1–32 (2020)
Su, H., Liu, S., Zheng, B., Zhou, X., Zheng, K.: A survey of trajectory distance measures and performance evaluation. VLDB J. 29(1), 3–32 (2020)
Su, H., Zheng, K., Wang, H., Huang, J., Zhou, X.: Calibrating trajectory data for similarity-based analysis. In: ACM SIGMOD, pp. 833–844 (2013)
Vlachos, M., Kollios, G., Gunopulos., D.: Discovering similar multidimensional trajectories. In: ICDE, pp. 673–684 (2002)
Wang, S., Bao, Z., Culpepper, J.S., Xie, Z., Liu, Q., Qin, X.: Torch: a search engine for trajectory data. In: The 41st ACM SIGIR, pp. 535–544 (2018)
Wang, S., Bao, Z., Culpepper, J., Sellis, T., Qin, X.: Fast large-scale trajectory clustering. Proc. VLDB Endowment 13(1), 29–42 (2019)
Wang, Y., Li, G., Tang, N.: Querying shortest paths on time dependent road networks. Proc. VLDB Endowment 12(11), 1249–1261 (2019)
Wang, Z., Long, C., Cong, G., Ju, C.: Effective and efficient sports play retrieval with deep representation learning. In: 25th ACM SIGKDD, p. 499–509 (2019)
Wang, Z., Long, C., Cong, G., Liu, Y.: Efficient and effective similar subtrajectory search with deep reinforcement learning. VLDB, p. 2312–2325 (2020)
Yao, D., Zhang, C., et al, Z.Z.: Trajectory clustering via deep representation learning. In: Proceedings of the IJCNN, pp. 3880–3887 (2017)
Yao, D. and Cong, G.e.a.: Computing trajectory similarity in linear time: a generic seed-guided neural metric learning approach. In: ICDE, p. 1358–1369 (2019)
Yi, B.K., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: ICDE, pp. 201–208 (1998)
Yuan, J., et al.: T-drive: driving directions based on taxi trajectories. In: SIGSPATIAL, pp. 99–108 (2010)
Zheng, Y., Liu, L., Wang, L., Xie, X.: Learning transportation mode from raw GPS data for geographic applications on the web. In: WWW, pp. 247–256 (2008)
Zhong, R., Li, G., Tan, K.L., Zhou, L., Gong, Z.: G-tree: an efficient and scalable index for spatial search on road networks. TKDE 27(8), 2175–2189 (2015)
Acknowledgments
The research work was supported by Shenyang Young and Middle-aged Scientific and Technological Innovation Talent Program (grant# RC220504); Natural Science Foundation of Liaoning Education Department (grant# LJKZ0205); Hong Kong Research Grants Council (grant# 16202722); Natural Science Foundation of China (grant# 62072125, grant# 61902134); partially conducted in the JC STEM Lab of Data Science Foundations funded by The Hong Kong Jockey Club Charities Trust.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Li, J., Wang, M., Li, L., Xin, K., Hua, W., Zhou, X. (2023). Trajectory Representation Learning Based on Road Network Partition for Similarity Computation. In: Wang, X., et al. Database Systems for Advanced Applications. DASFAA 2023. Lecture Notes in Computer Science, vol 13943. Springer, Cham. https://doi.org/10.1007/978-3-031-30637-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-031-30637-2_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30636-5
Online ISBN: 978-3-031-30637-2
eBook Packages: Computer ScienceComputer Science (R0)