Abstract
Increasingly applications require the storage and retrieval of spatio-temporal information in a database management system. A type of such information is mobile objects, i.e., objects whose location changes continuously with time. Various techniques have been proposed to address problems of incorporating such objects in databases. In this paper, we introduce new query processing techniques for dynamic queries over mobile objects, i.e., queries that are themselves continuously changing with time. Dynamic queries are natural in situational awareness systems when an observer is navigating through space. All objects visible by the observer must be retrieved and presented to her at very high rates, to ensure a high-quality visualization. We show how our proposed techniques offer a great performance improvement over a traditional approach of multiple instantaneous queries.
This work was supported in part by the National Science Foundation under Grant No. IIS-0086124, in part by the Army Research Laboratory under Cooperative Agreements No. DAAL-01-96-2-0003 and No. DAAD-19-00-1-0188, and in part by Air Force Grant F33615-01-C-1902. We thank the anonymous reviewers for their detailed and helpful comments.
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.
References
B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. VLDB Journal, 5(4):264–275, 1996.
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In ACM SIGMOD, 1990.
K. Chakrabarti, K. Porkaew, and S. Mehrotra. Efficient query refinement in multimedia databases. In IEEE ICDE 2000.
J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. NiagaraCQ: A scalable continuous query system for internet databa ses. In ACM SIGMOD, 2000.
A. Guttman. R-tree: a dynamic index structure for spatial searching. In ACM SIGMOD, 1984.
G. Hjaltason and H. Samet. Incremental distance join algorithms for spatial databases. In ACM SIGMOD, 1998.
G. R. Hjaltason and H. Samet. Ranking in spatial databases. In Int’l Symposium on Large Spatial Databases, 1995.
G. Kollios, D. Gunopulos, and V. J. Tsotras. On indexing mobile objects. In Symposium on Principles of Database Systems, 1999.
I. Lazaridis, K. Porkaew, and S. Mehrotra. Dynamic queries over mobile objects. (full version) Technical Report TR-DB-01-07, UC Irvine, 2001.
D. Lomet and B. Salzberg. The hB-Tree: A multiattribute indexing method with good guaranteed performance. ACM TODS, 15(4):625–658, 1990.
D. Lomet and B. Salzberg. The performance of a multiversion access method. In ACM SIGMOD, 1990.
D. Pfoser and C. Jensen. Capturing the uncertainty of moving-object representations. In SSD, 1999.
D. Pfoser, C. Jensen, and Y. Theodoridis. Novel approaches to the indexing of moving object trajectories. In VLDB, 2000.
K. Porkaew. Database support for similarity retrieval and querying mobile objects. Technical report, PhD thesis, University of Illinois at Urbana-Champaign, 2000.
K. Porkaew, I. Lazaridis, and S. Mehrotra. Querying mobile objects in spatiotemporal databases. In SSTD 2001, Redondo Beach, CA, USA.
J. T. Robinson. The k-d-b-tree: A search structure for large multidimensional dynamic indexes. In ACM SIGMOD, 1981.
N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In ACM SIGMOD, 1995.
S. Saltenis and C. Jensen. Indexing of moving objects for location-based services. In ICDE(to appear), 2002.
S. Saltenis, C. Jensen, S. Leutenegger, and M. Lopez. Indexing the positions of continuously moving objects. In ACM SIGMOD, 2000.
B. Salzberg and V. Tsotras. Comparison of access methods for time-evolving data. ACM Computing Surveys, 31(2):158–221, 1999.
H. Samet. The quadtree and related hierarchial data structures. ACM Computing Surveys, 16(2):187–260, 1984.
T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+ tree: A dynamic index for multi-dimensional objects. In VLDB, 1987.
A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Modeling and querying moving objects. In IEEE ICDE 1997.
Z. Song and N. Roussopoulos. K-nearest neighbor search for moving query point. In SSTD, 2001.
J. Tayeb, O. Ulusoy, and O. Wolfson. A quadtree based dynamic attribute indexing method. Computer Journal, 41(3):185–200, 1998.
D. B. Terry, D. Goldberg, D. Nichols, and B. M. Oki. Continuous queries over append-only databases. In ACM SIGMOD, 1992.
Y. Theodoridis, T. Sellis, A. N. Papadopoulos, and Y. Manolopoulos. Specifications for efficient indexing in spatiotemporal databases. In SSDBM, 1998.
O. Wolfson, S. Chamberlain, S. Dao, L. Jiang, and G. Mendez. Cost and imprecision in modeling the position of moving objects. In IEEE ICDE, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lazaridis, I., Porkaew, K., Mehrotra, S. (2002). Dynamic Queries over Mobile Objects. In: Jensen, C.S., et al. Advances in Database Technology — EDBT 2002. EDBT 2002. Lecture Notes in Computer Science, vol 2287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45876-X_18
Download citation
DOI: https://doi.org/10.1007/3-540-45876-X_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43324-8
Online ISBN: 978-3-540-45876-0
eBook Packages: Springer Book Archive