Abstract
The trajectory similarity join aims to find similar trajectory pairs from two large collections of trajectories. This join targets applications such as trajectory near-duplicate detection, ridesharing recommendation and so on. Extensive works have been conducted on addressing this join. However, most of them only focus on spatial dimension without combining temporal range together. To address problem, this paper proposes a novel two-level grid index which takes both spatial and temporal range into account when processing spatial-temporal similarity join, and signature based dynamic grid warping (SDGW) approach to evaluate the spatial similarity for trajectory pairs. Some pruning approaches are developed to improve the query processing. In addition, extensive experiments are conducted to verify the efficiency and scalability of our methods.
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
Assent, I., Wichterich, M., Krieger, R., Kremer, H., Seidl, T.: Anticipatory DTW for efficient similarity search in time series databases. Proc. VLDB 2(1), 826–837 (2009)
Bakalov, P., Hadjieleftheriou, M., Keogh, E.J., Tsotras, V.J.: Efficient trajectory joins using symbolic representation. In: International Conference on Mobile Data Management (2005)
Bakalov, P., Tsotras, V.J.: Continuous spatiotemporal trajectory joins. In: Nittel, S., Labrinidis, A., Stefanidis, A. (eds.) GSN 2006. LNCS, vol. 4540, pp. 109–128. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79996-2_7
Chen, Z., Shen, H.T., Zhou, X., Zheng, Y., Xie, X.: Searching trajectories by locations: an efficiency study. In: International Conference on Management of Data, pp. 255–266. Association for Computing Machinery Special Interest Group (2010)
Frentzos, E., Gratsias, K., Theodoridis, Y.: Index-based most similar trajectory search. In: IEEE International Conference on Data Engineering (2007)
Hui, D., Trajcevski, G., Scheuermann, P.: Efficient similarity join of large sets of moving object trajectories. In: International Symposium on Temporal Representation and Reasoning (2008)
Lei, C., Ng, R.: On the marriage of Lp-norms and edit distance. In: Proceedings of the VLDB, pp. 792–803 (2004)
Lei, C., Ozsu, 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 (2005)
Lin, B., Su, J.: Shapes based trajectory queries for moving objects, pp. 21–30 (2005)
Lu, J., Wu, D., Mao, M., Wang, W., Zhang, G.: Recommender system application developments. Decis. Support Syst. 74(C), 12–32 (2015)
Morse, M.D., Patel, J.M.: An efficient and accurate method for evaluating time series similarity. In: ACM SIGMOD, pp. 569–580 (2007)
Na, T., et al.: Signature-based trajectory similarity join. IEEE Trans. Knowl. Data Eng. 29(4), 870–883 (2017)
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: Proceedings of the VLDB, vol. 29, pp. 802–813 (2003)
Ranu, S., Deepak, P., Telang, A.D., Deshpande, P., Raghavan, S.: Indexing and matching trajectories under inconsistent sampling rates. In: IEEE ICDE, pp. 999–1010 (2015)
Sakurai, Y., Yoshikawa, M., Faloutsos, C.: FTW: fast similarity search under the time warping distance. In: Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (2005)
Sankararaman, S., Agarwal, P.K., Mølhave, T., Pan, J., Boedihardjo, A.P.: Model-driven matching and segmentation of trajectories. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 234–243 (2013)
Shang, S., Chen, L., Wei, Z., Jensen, C.S., Zheng, K., Kalnis, P.: Trajectory similarity join in spatial networks. Proc. VLDB 10(11), 1178–1189 (2017)
Shang, S., Ding, R., Yuan, B., Xie, K., Zheng, K., Kalnis, P.: User oriented trajectory search for trip recommendation. In: EDBT, pp. 156–167 (2012)
Shang, S., Ding, R., Zheng, K., Jensen, C.S., Kalnis, P., Zhou, X.: Personalized trajectory matching in spatial networks. VLDB J. 23(3), 449–468 (2014)
Vaid, S., Jones, C.B., Joho, H., Sanderson, M.: Spatio-textual indexing for geographical search on the web. In: Bauzer Medeiros, C., Egenhofer, M.J., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 218–235. Springer, Heidelberg (2005). https://doi.org/10.1007/11535331_13
Vlachos, M., Gunopoulos, D., Kollios, G.: Discovering similar multidimensional trajectories. In: IEEE ICDE, pp. 673–684 (2002)
Wang, X., Mueen, A., Ding, H., Trajcevski, G., Scheuermann, P., Keogh, E.: Experimental comparison of representation methods and distance measures for time series data. Data Min. Knowl. Disc. 26(2), 275–309 (2013)
Yi, B.K., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: IEEE ICDE, pp. 201–208 (1998)
Yun, C., Patel, J.M.: Design and evaluation of trajectory join algorithms. In: ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2009)
Acknowledgments
This work is supported in part by Hubei Natural Science Foundation under Grant No. 2017CFB135, and the Fundamental Research Funds for the Central Universities under Grants No. CCNU18QN017, CZZ17003, and Teaching Research Projects NO. JYX17032, and NSFC Grant No. 61309002.
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
Dan, T., Luo, C., Li, Y., Zhang, C. (2019). Trajectory Similarity Join for Spatial Temporal Database. In: Hartmann, S., Küng, J., Chakravarthy, S., Anderst-Kotsis, G., Tjoa, A., Khalil, I. (eds) Database and Expert Systems Applications. DEXA 2019. Lecture Notes in Computer Science(), vol 11707. Springer, Cham. https://doi.org/10.1007/978-3-030-27618-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-27618-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-27617-1
Online ISBN: 978-3-030-27618-8
eBook Packages: Computer ScienceComputer Science (R0)