LUGrid: Update-tolerant Grid-based Indexing for Moving Objects
Abstract
Indexing moving objects is a fundamental issue in spatiotemporal databases. In this paper, we propose an adaptive Lazy-Update Grid-based index (LUGrid, for short) that minimizes the cost of object updates. LUGrid is designed with two important features, namely, lazy insertion and lazy deletion. Lazy insertion reduces the update I/Os by adding an additional memory-resident layer over the disk index. Lazy deletion reduces update cost by avoiding deleting single obsolete entry immediately. Instead, the obsolete entries are removed later by specially designed mechanisms. LUGrid adapts to object distributions through cell splitting and merging. Theoretical analysis and experimental results indicate that LUGrid outperforms former work by up to eight times when processing intensive updates, while yielding similar search performance.
Keywords
indexing, spatiotemporal databasdes, grid based index, object distributions
Date of this Version
5-2006
Comments
7th International Conference on Mobile Data Management (MDM'06) Nara, Japan, May 10-May 12, 2006