Shapes based trajectory queries for moving objects

ABSTRACT

An interesting issue in moving objects databases is to find similar trajectories of moving objects. Previous work on this topic focuses on movement patterns (trajectories with time dimension) of moving objects, rather than spatial shapes (trajectories without time dimension) of their trajectories. In this paper we propose a simple and effective way to compare spatial shapes of moving object trajectories. We introduce a new distance function based on ``one way distance'' (OWD). Algorithms for evaluating OWD in both continuous (piece wise linear) and discrete (grid representation) cases are developed. An index structure for OWD in grid representation, which guarantees no false dismissals, is also given to improve the efficiency of similarity search. Empirical studies show that OWD out-performs existent methods not only in precision, but also in efficiency. And the results of OWD in continuous case can be approximated by discrete case efficiently.

REFERENCES

• 1: T. Brinkhoff. Generating traffic data. Bulletin of the Technical Committee on Data Engineering, IEEE Computer Society, 26(2):19--25, 2003.
• 2: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 3: L. Chen and R. Ng. On the marriage of lp-norms and edit distance. In Proc. VLDB, 2004.
• 4: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 8: E. Keogh, T. Palpanas, V. B. Zordan, D. Gunopulos, and M. Cardle. Indexing large human-motion databases. In Proc. VLDB, 2004.
• 9: S. L. Lee, S. J. Chun, D. H. Kim, J. H. Lee, and C. W. Chung. Similarity search for multidimensional data sequences. In Proc. Int. Conf. on Data Engineering, 2005.
• 10: J. L. Little and Z. Gu. Video retrieval by spatial and temporal sturcture of trajectories. In Proc. of Symp. on Storage and Retrieval for Image and Video Databases, 2001.
• 11: Nirvana Meratnia , Rolf A. de By, Aggregation and comparison of trajectories, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585158]
• 12: Yuhan Cai , Raymond Ng, Indexing spatio-temporal trajectories with Chebyshev polynomials, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007636]
• 13: Victor Pan, Complexity of computations with matrices and polynomials, SIAM Review, v.34 n.2, p.225-262, June 1992 [doi>10.1137/1034049]
• 14: Yasushi Sakurai , Masatoshi Yoshikawa , Christos Faloutsos, FTW: fast similarity search under the time warping distance, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065210]
• 15: D. Sankoff and J. B. Kruskal. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparisons. Addison-Wesley, 1983.
• 16: Michail Vlachos , D. Gunopulos , Gautam Das, Rotation invariant distance measures for trajectories, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014144]
• 17: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 18: Yutaka Yanagisawa , Jun-ichi Akahani , Tetsuji Satoh, Shape-Based Similarity Query for Trajectory of Mobile Objects, Proceedings of the 4th International Conference on Mobile Data Management, p.63-77, January 21-24, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance

Keywords:
moving object trajectories, one way distance, similarity search, spatial shape