Dynamics-aware similarity of moving objects trajectories

ABSTRACT

This work addresses the problem of obtaining the degree of similarity between trajectories of moving objects. Typically, a Moving Objects Database (MOD) contains sequences of (location, time) points describing the motion of individual objects, however, they also implicitly storethe velocity -- an important attribute describing the dynamics the motion. Our main goal is to extend the MOD capability with reasoning about how similar are the trajectories of objects, possibly moving along geographically different routes. We use a distance function which balances the lack of temporal-awareness of the Hausdorff distance with the generality (and complexity of calculation) of the Fréchet distance. Based on the observation that in practice the individual segments of trajectories are assumed to have constant speed, we provide efficient algorithms for: (1) optimal matching between trajectories; and (2) approximate matching between trajectories, both under translations and rotations, where the approximate algorithm guarantees a bounded error with respect to the optimal one.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: Helmut Alt , Christian Knauer , Carola Wenk, Comparison of Distance Measures for Planar Curves, Algorithmica, v.38 n.1, p.45-58, October 2003 [doi>10.1007/s00453-003-1042-5]
• 3: Helmut Alt , Oswin Aichholzer , Günter Rote, Matching shapes with a reference point, Proceedings of the tenth annual symposium on Computational geometry, p.85-92, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177555]
• 4: Helmut Alt , Alon Efrat , Günter Rote , Carola Wenk, Matching planar maps, Journal of Algorithms, v.49 n.2, p.262-283, November 2003 [doi>10.1016/S0196-6774(03)00085-3]
• 5: H. Alt and L. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In Handbook of Computational Geometry, 1999.
• 6: Helmut Alt , Christian Knauer , Carola Wenk, Matching Polygonal Curves with Respect to the Fréchet Distance, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.63-74, February 15-17, 2001
• 7: Boris Aronov , Sariel Har-Peled , Christian Knauer , Yusu Wang , Carola Wenk, Fréchet distance for curves, revisited, Proceedings of the 14th conference on Annual European Symposium, p.52-63, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_8]
• 8: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 9: Petko Bakalov , Marios Hadjieleftheriou , Vassilis J. Tsotras, Time relaxed spatiotemporal trajectory joins, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097091]
• 10: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594]
• 11: Hu Cao , Ouri Wolfson , Goce Trajcevski, Spatio-temporal data reduction with deterministic error bounds, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.211-228, September 2006 [doi>10.1007/s00778-005-0163-7]
• 12: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 13: S. E. Dreyfus. An appraisal of some shortest -- path algorithms. Operations Research, 17(3), 1969.
• 14: C. du Mouza and R. Rigaux. Multi-scale classification of moving objects trajectories. In SSDBM, 2004.
• 15: Alon Efrat , Quanfu Fan , Suresh Venkatasubramanian, Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves, Journal of Mathematical Imaging and Vision, v.27 n.3, p.203-216, April 2007 [doi>10.1007/s10851-006-0647-0]
• 16: T. Eiter and H. Mannila. Distance measures for point sets and their computation. Acta Inf., 34(2), 1997.
• 17: Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Approximate Geometric Pattern Matching Under Rigid Motions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.4, p.371-379, April 1999 [doi>10.1109/34.761267]
• 18: Hartmut Güting , Teixeira de Almeida , Zhiming Ding, Modeling and querying moving objects in networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.165-190, June 2006 [doi>10.1007/s00778-005-0152-x]
• 19: R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.
• 20: Marios Hadjieleftheriou , George Kollios , Petko Bakalov , Vassilis J. Tsotras, Complex spatio-temporal pattern queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 21: Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142697]
• 22: K. Imai, S. Sumino, and H. Imai. Minimax geometric fitting of two corresponding sets of points and dynamic furthest voronoi diagrams. IEICE Trans. Inf. and Syst., E81-D(11), 1998.
• 23: Forbes Online Issue http://www.forbes.com/home, April 2006.
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 26: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 27: Goce Trajcevski , Ouri Wolfson , Klaus Hinrichs , Sam Chamberlain, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), v.29 n.3, p.463-507, September 2004 [doi>10.1145/1016028.1016030]
• 28: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing Multidimensional Time-Series, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.1-20, January 2006 [doi>10.1007/s00778-004-0144-2]
• 29: Michail Vlachos , George Kollios , Dimitrios Gunopulos, Elastic Translation Invariant Matching of Trajectories, Machine Learning, v.58 n.2-3, p.301-334, February 2005 [doi>10.1007/s10994-005-5830-9]
• 30: Carola Wenk , Randall Salas , Dieter Pfoser, Addressing the Need for Map-Matching Speed: Localizing Globalb Curve-Matching Algorithms, Proceedings of the 18th International Conference on Scientific and Statistical Database Management, p.379-388, July 03-05, 2006 [doi>10.1109/SSDBM.2006.11]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Keywords:
dynamics, similarity, trajectories