On moving object queries
- 3 June 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 188-198
- https://doi.org/10.1145/543613.543638
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 R. Queries in this language may be past, continuing, or future. We show that iff 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.Keywords
This publication has 18 references indexed in Scilit:
- A foundation for representing and querying moving objectsACM Transactions on Database Systems, 2000
- Indexing moving points (extended abstract)Published by Association for Computing Machinery (ACM) ,2000
- On indexing mobile objectsPublished by Association for Computing Machinery (ACM) ,1999
- Arity Bounds in First-Order Incremental Evaluation and Definition of Polynomial Time Database QueriesJournal of Computer and System Sciences, 1998
- Constraint Query LanguagesJournal of Computer and System Sciences, 1995
- Incremental and Decremental Evaluation of Transitive Closure by First-Order QueriesInformation and Computation, 1995
- Complexity of Computations with Matrices and PolynomialsSIAM Review, 1992
- On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the realsJournal of Symbolic Computation, 1992
- Incremental recomputation of active relational expressionsIEEE Transactions on Knowledge and Data Engineering, 1991
- The complexity of elementary algebra and geometryJournal of Computer and System Sciences, 1986