On indexing mobile objects
George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras · 1999
We show how to index mobile objects in one and two dimensions using efficient dynamic external memory data structures.The problem is motivated by real life applications in traffic monitoring, intelligent navigation and mobile communications domains.For the l-dimensional case, we give (i) a dynamic, external memory algorithm with guaranteed worst case performance and linear 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.Initial experimental results and comparisons to traditional indexing approaches are also included.Permission to make digital or hard copies or all or part of this work fin personal or classroom use is granted without fee provided that copies are not made or distributed for profit or cornmerrial advantage and that copies hear this notice and the full citation on the tirst page.TO copy otherwise, to