Q+Rtree: efficient indexing for moving object databases

Moving object environments contain large numbers of queries and continuously moving objects. Traditional spatial index structures do not work well in this environment because of the need to frequently update the index which results in very poor performance. In this paper, we present a novel indexing...

Full description

Saved in:
Bibliographic Details
Main Authors: Yuni Xia, Prabhakar, S.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Degradation
Indexing
Query processing
Spatial databases
Spatial indexes
Surfaces
Switches
Traffic control
Tree data structures
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Moving object environments contain large numbers of queries and continuously moving objects. Traditional spatial index structures do not work well in this environment because of the need to frequently update the index which results in very poor performance. In this paper, we present a novel indexing structure, namely the Q+Rtree, based on the observation that: i) most moving objects are in quasi-static state most of time, and ii) the moving patterns of objects are strongly related to the topography of the space. The Q+Rtree is a hybrid tree structure which consists of both an R*tree and a QuadTree. The R*tree component indexes quasi-static objects ie., those that are currently moving slowly and are often crowded together in buildings or houses. The Quadtree component indexes fast moving objects which are dispersed over wider regions. We also present the experimental evaluation of our approach.
DOI:10.1109/DASFAA.2003.1192381