LUGrid: Update-tolerant Grid-based Indexing for Moving Objects

Get BibTex-formatted data

Author

X Xiong, MF Mokbel, WG Aref

Entry type

inproceedings

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.

Date

2006

Booktitle

Proceedings of the 7th International Conference on Mobile Data Management

Journal

International Conference On Mobile Data Management

Key alpha

Aref

Publisher

IEEE Computer Society

Publication Date

2006-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Aref,
	title = "LUGrid: Update-tolerant Grid-based Indexing for Moving Objects",
	author = "X Xiong, MF Mokbel, WG Aref",
	year = "2006",
	booktitle = "Proceedings of the 7th International Conference on Mobile Data Management",
	journal = "International Conference On Mobile Data Management",
	pages = "13",
	publisher = "IEEE Computer Society",
	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.",
}