Abstract
With the rapid accumulation of GPS trajectory data, the vast amount of spatiotemporal trajectory data hides extremely rich and valuable information with potential travel behavior patterns. The similarity of the driver’s travel trajectory is key to mining patterns, but how to reasonably and efficiently evaluate the similarity remains a challenge. To address this problem, we propose a driving trajectory similarity measurement using grid-based dynamic time warping (GDTW) to evaluate similarity of driving trajectory. Building trajectory grid vector model (TGVM), the method solves the problems of position shift and large computation for the similarity measuring of big trajectory data. Extensive experiments were conducted with a real trajectory dataset to evaluate feasibility and efficiency of the proposed approaches. The results show that GDTW performs a more robust and efficient processing of trajectory similarity than does traditional approaches, reducing by about 5 times of time-consuming.
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
References
Liao, L., Wu, J., Zou, F., et al.: Trajectory topic modelling to characterize driving behaviors with GPS-based trajectory data. J. Internet Technol. 19(3), 815–824 (2018)
Carboni, EM., Bogorny, V.: Inferring drivers behavior through trajectory analysis. In: Intelligent Systems 2014, pp. 837–848. Springer, Cham (2015)
Shang, S., Chen, L., Wei, Z., et al.: Trajectory similarity join in spatial networks. Proc. VLDB Endow. 10(11), 1178–1189 (2017)
Li, Y., Su, H., Demiryurek, U., et al.: PaRE: a system for personalized route guidance. In: Proceedings of the 26th International Conference on World Wide Web, pp. 637–646. International World Wide Web Conferences Steering Committee (2017)
Long, J.A., Nelson, T.A.: A review of quantitative methods for movement data. Int. J. Geograph. Inf. Sci. 27(2), 292–318 (2013)
Sankararaman, S., Agarwal, P.K., Mølhave, T., et al.: Computing similarity between a pair of trajectories. arXiv preprint arXiv:1303.1585 (2013)
Atev, S., Miller, G., Papanikolopoulos, N.P.: Clustering of vehicle trajectories. IEEE Trans. Intell. Transp. Syst. 11(3), 647–657 (2010)
Kahveci, T., Singh, A., Gurel, A.: Similarity searching for multi-attribute sequences. In: Proceedings of the 14th International Conference on Scientific and Statistical Database Management, pp. 175–184. IEEE (2002)
Furtado, A.S., Kopanaki, D., Alvares, L.O., et al.: Multidimensional similarity measuring for semantic trajectories. Trans. GIS 20(2), 280–298 (2016)
Toohey, K., Duckham, M.: Trajectory similarity measures. Sigspatial Spec. 7(1), 43–50 (2015)
Kang, H.Y., Kim, J.S., Li, K.J.: Similarity measures for trajectory of moving objects in cellular space. In: Proceedings of the 2009 ACM Symposium on Applied Computing, pp. 1325–1330. ACM (2009)
Lin, B., Su, J.: One way distance: For shape based similarity search of moving object trajectories. GeoInformatica 12(2), 117–142 (2008)
Lim, E.C., Shim, C.B.: Similarity search algorithm for efficient sub-trajectory matching in moving databases. In: International Conference on Computational Science, pp. 821–828. Springer, Heidelberg (2007)
Sakurai, Y., Yoshikawa, M., Faloutsos, C.: FTW: fast similarity search under the time warping distance. In: Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 326–337. ACM (2005)
Hu, W., Li, X., Tian, G., et al.: An incremental DPMM-based method for trajectory clustering, modeling, and retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 35(5), 1051–1065 (2013)
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pp. 491–502. ACM (2005)
Itakura, F.: Minimum prediction residual principle applied to speech recognition. IEEE Trans. Acoust. Speech Signal Process. 23(1), 67–72 (1975)
Acknowledgment
This work was supported in part by Projects of National Science Foundation of China (No. 41471333); project 2017A13025 of Science and Technology Development Center, Ministry of Education, China; project 2018Y3001 of Fujian Provincial Department of Science and Technology; projects of Fujian Provincial Department of Education (JA14209, JA15325). Fujian Provincial Department of Transportation is also acknowledged for supporting the experimental dataset.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Cai, Q., Liao, L., Zou, F., Song, S., Liu, J., Zhang, M. (2019). Trajectory Similarity Measuring with Grid-Based DTW. In: Zhao, Y., Wu, TY., Chang, TH., Pan, JS., Jain, L. (eds) Advances in Smart Vehicular Technology, Transportation, Communication and Applications. VTCA 2018. Smart Innovation, Systems and Technologies, vol 128. Springer, Cham. https://doi.org/10.1007/978-3-030-04585-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-04585-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04584-5
Online ISBN: 978-3-030-04585-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)