On indexing mobile objects

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.