Abstract
Similarity query is one of the most important operations in trajectory databases and this paper addresses this problem in RFID trajectory databases. Due to the special sensing manner, the model of RFID trajectory is different from the traditional trajectory, leading to the inefficiency of existing techniques. This paper proposes a novel distance function—EDEU(Edit Distance combined with Euclidean Distance), which supports the local time shifting and takes the distance between adjacent logic areas into consideration. We also develop two filter-refinement mechanisms based on Co-occurrence Degree and Length Dispersion Ratio to improve the efficiency of the similarity analysis. Furthermore, we extend our solution to determine the local similarity from the global dissimilarity trajectory pairs. The extensive experiments verify the efficiency of our proposed algorithms.
The research was supported by the NSF of China under Grants No. 60773220 and the Fundamental Research Funds for the Central Universities No. N090904013.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
André-Jönsson, H., Badal, D.Z.: Using signature files for querying time-series data. In: Komorowski, J., Żytkow, J.M. (eds.) PKDD 1997. LNCS, vol. 1263, Springer, Heidelberg (1997)
Chang, J., Bista, R., Kim, J., Kim, Y.: A new trajectory search algorithm based on spatio-temporal similarity on spatial network. In: CIT 2007, pp. 110–115 (2007)
Chen, L., Ng, R.: On the marriage of lp-norms and edit distance. In: VLDB ’04, pp. 792–803 (2004)
Chen, L., Özsu, M., Oria, V.: Robust and fast similarity search for moving object trajectories. In: SIGMOD ’05, pp. 491–502 (2005)
Frentzos, E., Gratsias, K., Theodoridis, Y.: Index-based most similar trajectory search. In: ICDE ’07, pp. 816–825 (2007)
Lee, C., Chung, C.: Efficient storage scheme and query processing for supply chain management using rfid. In: SIGMOD ’08, pp. 291–302 (2008)
Mannila, H., Ronkainen, P.: Similarity of event sequences. In: Temporal Representation and Reasoning ’97, pp. 136–139 (1997)
Masciari, E.: Rfid data management for effective objects tracking. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 457–461. Springer, Heidelberg (2007)
Sarawagi, S., Kirpal, A.: Efficient set joins on similarity predicates. In: SIGMOD ’04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pp. 743–754. ACM, New York (2004)
Vlachos, M., Gunopoulos, D., Kollios, G.: Discovering similar multidimensional trajectories. In: ICDE 2002, p. 673 (2002)
Xiao, C., Wang, W., Lin, X.: Ed-join: an efficient algorithm for similarity joins with edit distance constraints. Proc. VLDB Endow. 1(1), 933–944 (2008)
Yanagisawa, Y., Akahani, T., Satoh, J.: Shape-based similarity query for trajectory of mobile objects. In: Chen, M.-S., Chrysanthis, P.K., Sloman, M., Zaslavsky, A. (eds.) MDM 2003. LNCS, vol. 2574, pp. 63–77. Springer, Heidelberg (2003)
Yang, B., Lu, H., Jensen, C.S.: Scalable continuous range monitoring of moving objects in symbolic indoor space. In: CIKM ’09, pp. 671–680 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Y., Yu, G., Gu, Y., Yue, D., Zhang, T. (2010). Efficient Similarity Query in RFID Trajectory Databases. In: Chen, L., Tang, C., Yang, J., Gao, Y. (eds) Web-Age Information Management. WAIM 2010. Lecture Notes in Computer Science, vol 6184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14246-8_60
Download citation
DOI: https://doi.org/10.1007/978-3-642-14246-8_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14245-1
Online ISBN: 978-3-642-14246-8
eBook Packages: Computer ScienceComputer Science (R0)