International Conference on Transportation and Development 2019
Deep Trajectory Similarity Model: A Fast Method for Trajectory Similarity Computation
Publication: International Conference on Transportation and Development 2019: Innovation and Sustainability in Smart Mobility and Smart Cities
ABSTRACT
Measuring trajectory similarity is a fundamental problem in the trajectory data mining field, and many similarity measurement methods had been proposed, such as dynamic time wrapping (DTW). However, these methods are dynamic programming problems, and dynamic programming problem usually leads to quadratic computational complexity. Thus, many acceleration algorithms were proposed. In this article, we proposed a deep neural network (DNN) based supervised similarity model, deep trajectory similarity model, to fit DTW similarity and to keep accuracy and orderliness. In the training process, we used low-frequency GPS trajectory data in Beijing as input data and used the DTW similarity of trajectory pairs as labels. In the test process, the model predicted the DTW similarity between two GPS trajectories. Experiments in this article indicated that deep trajectory similarity model could greatly decrease over 20% computation time than the acceleration algorithm of DTW similarity, FastDTW algorithm, and keep over 90% accuracy and over 97% orderliness. Experiments result indicated that the DTSM model has great potential in big data scenario.
Get full access to this chapter
View all available purchase options and get full access to this chapter.
ACKNOWLEDGMENTS
This work is supported by National Key R&D Program in China (2016YFB0100906), National Natural Science Foundation of China under Grant No. 61673232 and Tsinghua University Initiative Scientific Research Program (20183080016) and Director Funding of National Engineering Lab for Public Security Risk Perception and Control by Big Data. Data is supported by Dr. Chuanjiu Wang and his company.
REFERENCE
Bromley, J., Guyon, I., LeCun, Y., Säckinger, E., & Shah, R. (1994). Signature verification using a" siamese" time delay neural network. In Advances in neural information processing systems (pp. 737-744).
Chen, C., Liao, C., Xie, X., Wang, Y., & Zhao, J. (2018). Trip2Vec: a deep embedding approach for clustering and profiling taxi trip purposes. Personal and Ubiquitous Computing, 1-14.
Huang, P. S., He, X., Gao, J., Deng, L., Acero, A., & Heck, L. (2013, October). Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Conference on information & knowledge management (pp. 2333-2338). ACM.
Jiang, X., de Souza, E. N., Pesaranghader, A., Hu, B., Silver, D. L., & Matwin, S. (2017). Trajectorynet: An embedded gps trajectory representation for point-based classification using recurrent neural networks. arXiv preprint arXiv:1705.02636.
Mazimpaka, J. D., & Timpf, S. (2016). Trajectory data mining: A review of methods and applications. Journal of Spatial Information Science, 2016(13), 61-99.
Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781.
Salvador, S., & Chan, P. (2007). Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5), 561-580.
Sardá-Espinosa, A. (2017). Comparing time-series clustering algorithms in r using the dtwclust package. R package vignette, 12.
Senin, P. (2008). Dynamic time warping algorithm review. Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 855, 1-23.
Soheily-Khah, S., Douzal-Chouakria, A., & Gaussier, E. (2016). Generalized k-means-based clustering for temporal data under weighted and kernel time warp. Pattern Recognition Letters, 75, 63-69.
Yao, D., Zhang, C., Zhu, Z., Huang, J., & Bi, J. (2017, May). Trajectory clustering via deep representation learning. In Neural Networks (IJCNN), 2017 International Joint Conference on (pp. 3880-3887). IEEE.
Information & Authors
Information
Published In
International Conference on Transportation and Development 2019: Innovation and Sustainability in Smart Mobility and Smart Cities
Pages: 13 - 23
Editor: David A. Noyce, Ph.D., University of Wisconsin–Madison
ISBN (Online): 978-0-7844-8258-2
Copyright
© 2019 American Society of Civil Engineers.
History
Published online: Aug 28, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.