Handling Frequent Updates of Moving Objects *

Abstract

A critical issue in moving object databases is to develop appropriate indexing structures for continuously moving object locations so that queries can still be performed efficiently. However, such location changes typically cause a high volume of updates, which in turn poses serious problems on maintaining index structures. In this paper we propose a Lazy Group Update (LGU) algorithm for disk-based index structures of moving objects. LGU contains two key additional structures to group " similar " updates so that they can be performed together: a disk-based insertion buffer (I-Buffer) for each internal node, and a memory-based deletion table (D-Table) for the entire tree. Different strategies of " pushing down " an overflow I-Buffer to the next level are studied. Comprehensive empirical studies over uniform and skewed datasets, as well as simulated street traffic data show that LGU achieves a significant improvement on update throughput while allowing a reasonable performance for queries.