On indexing mobile objects
- 1 May 1999
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 261-272
- https://doi.org/10.1145/303976.304002
Abstract
We show how to index mobile objects in one and two di- mensions using efficient dynamic external memory data structures. The problem is motivated by real life appli- cations in traffic monitoring, intelligent navigation and mobile communications domains. For the l-dimensional case, we give (i) a dynamic, external memory algo- rithm with guaranteed worst case performance and lin- ear space and (ii) a practical approximation algorithm also in the dynamic, external memory setting, which has linear space and expected logarithmic query time. We also give an algorithm with guaranteed logarithmic query time for a restricted version of the problem. We present extensions of our techniques to two dimensions. In addition we give a lower bound on the number of I/O's needed to answer the d-dimensional problem. Ini- tial experimental results and comparisons to traditional indexing approaches are also included.Keywords
This publication has 19 references indexed in Scilit:
- Comparison of access methods for time-evolving dataACM Computing Surveys, 1999
- Multidimensional access methodsACM Computing Surveys, 1998
- A Quadtree-Based Dynamic Attribute Indexing MethodThe Computer Journal, 1998
- Designing access methods for bitemporal databasesIEEE Transactions on Knowledge and Data Engineering, 1998
- Towards optimal two-dimensional indexing for constraint databasesInformation Processing Letters, 1997
- An asymptotically optimal multiversion B-treeThe VLDB Journal, 1996
- Efficient partition treesDiscrete & Computational Geometry, 1992
- The input/output complexity of sorting and related problemsCommunications of the ACM, 1988
- Searching and storing similar listsJournal of Algorithms, 1986
- Ubiquitous B-TreeACM Computing Surveys, 1979