On moving object queries: (extended abstract)

ABSTRACT

Database applications for moving objects pose new challenges in modeling, querying, and maintenance of objects whose locations are rapidly changing over time. Previous work on modeling and querying spatio-temporal databases and constraint databases focus primarily on snapshots of changing databases. In this paper we study query evaluation techniques for moving object databases where moving objects are being updated frequently. We consider a constraint database approach to moving objects and queries. We classify moving object queries into: "past", "continuing", and "future" queries. We argue that while traditional constraint query evaluation techniques are suitable for past queries, new techniques are needed for continuing and future queries. Motivated by nearest-neighbor queries, we define a query language based on a single "generalized distance" function f mapping from objects to continuous functions from time to ℝ. Queries in this language may be past, continuing, or future. We show that if f maps to polynomials, queries can be evaluated efficiently using the plane sweeping technique from computational geometry. Consequently, many known distance based queries can be evaluated efficiently.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• 3: J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. on Computers, 28:643-647, 1979.
• 4: Jan Chomicki , Peter Z. Revesz, A Geometric Framework for Specifying Spatiotemporal Objects, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.41, May 01-02, 1999
• 5: J. Chomicki and P. Z. Revesz. Parametric spatiotemporal objects. Bulletin AI*AI, 14(1):41-47, Mar. 2001.
• 6: Latha S. Colby , Timothy Griffin , Leonid Libkin , Inderpal Singh Mumick , Howard Trickey, Algorithms for deferred view maintenance, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.469-480, June 04-06, 1996, Montreal, Quebec, Canada
• 7: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 8: Guozhu Dong , Jianwen Su, Incremental and decremental evaluation of transitive closure by first-order queries, Information and Computation, v.120 n.1, p.101-106, July 1995 [doi>10.1006/inco.1995.1102]
• 9: Guozhu Dong , Jianwen Su, Arity bounds in first-order incremental evaluation and definition of polynomial time database queries, Journal of Computer and System Sciences, v.57 n.3, p.289-308, Dec. 1998 [doi>10.1006/jcss.1998.1565]
• 10: Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis, Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases, Geoinformatica, v.3 n.3, p.269-296, September 1999 [doi>10.1023/A:1009805532638]
• 11: Luca Forlizzi , Ralf Hartmut Güting , Enrico Nardelli , Markus Schneider, A data model and data structures for moving objects databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.319-330, May 15-18, 2000, Dallas, Texas, United States
• 12: Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States
• 13: A. Gupta and I. S. Mumick. Materialized Views. MIT Press, 1999.
• 14: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 15: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 16: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 17: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 18: Gabriel Kuper , Jan Paredaens , Leonid Libkin, Constraint Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 19: R. S. Millman and G. D. Parker. Elements of Differential Geometry. Prentice-Hall, Edgewood Cliffs, NJ, 1977.
• 20: Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, New York, NY, 1998
• 21: Victor Pan, Complexity of computations with matrices and polynomials, SIAM Review, v.34 n.2, p.225-262, June 1992 [doi>10.1137/1034049]
• 22: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 23: X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991 [doi>10.1109/69.91063]
• 24: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• 25: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 26: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 27: Jianwen Su , Haiyan Xu , Oscar H. Ibarra, Moving Objects: Logical Relationships and Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.3-19, July 12-15, 2001
• 28: A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, California, 1951.
• 29: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001
• 30: Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 31: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Design, Languages, Performance