Abstract
Similarity measure scheme on moving objects has become a topic of increasing in the area of moving databases. In this paper, we propose a new similarity search algorithm for efficient sub-trajectory matching. For measuring similarity between two sub-trajectories, we propose a new v(variable)-warping distance algorithm which enhances the existing time warping distance algorithm by permitting up to v replications for an arbitrary motion of a query trajectory. Our v-warping distance algorithm provides an approximate matching between two trajectories as well as an exact matching between them. Based on our v-warping distance algorithm, we also present a similarity measure scheme for the single trajectory in moving databases. Finally, we show that our scheme based on the v-warping distance achieves much better performance than other conventional schemes, such as Li’s one (no-warping) and Shan’s one (infinite-warping) in terms of precision and recall measures.
Chapter PDF
Similar content being viewed by others
References
Forlizzi, L., Guting, R.H., Nardelli, E., Schneider, M.: A Data Model and Data Structures for Moving Objects Databases. In: Proc. of ACM SIGMOD Conf., pp. 319–330 (2000)
Li, J., Ozsu, M.T., Szafron, D.: Modeling Video Temporal Relationships in an Object Database Management System. In: Proceedings of Multimedia Computing and Networking (MMCN97), pp. 80–91 (1997)
Shan, M., Lee, S.Y.: Content-based Video Retrieval via Motion Trajectories. In: Proceedings of SPIE Electronic Imaging and Multimedia System II, vol. 3561, pp. 52–61 (1998)
Yi, B., Lagadish, H.V., Faloutsos, C.: Efficient Retrieval of Similar Time Sequences Under Time Warping. In: Proc. Int’l. Conf. on Data Engineering, pp. 201–208. IEEE Computer Society Press, Los Alamitos (1998)
Park, S.H., et al.: Efficient Searches for Simialr Subsequence of Difference Lengths in Sequence Databases. In: Proc. Int’l. Conf. on Data Engineering, pp. 23–32. IEEE Computer Society Press, Los Alamitos (2000)
Salton, G., McGill, M.: An introduction to Modern Information Retrieval. McGraw-Hill, New York (1993)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Lim, EC., Shim, CB. (2007). Similarity Search Algorithm for Efficient Sub-trajectory Matching in Moving Databases. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2007. ICCS 2007. Lecture Notes in Computer Science, vol 4489. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72588-6_132
Download citation
DOI: https://doi.org/10.1007/978-3-540-72588-6_132
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72587-9
Online ISBN: 978-3-540-72588-6
eBook Packages: Computer ScienceComputer Science (R0)