Title

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

Share

COinS