Indexing for Dynamic Abstract Regions

Joxan Jaffar, Roland H.C. Yap, Kenny Q. Zhu

Abstract

We propose a new main memory index structure for abstract regions (objects) which may heavily overlap. These objects are ``dynamic'' as they have relatively short life span. The novelty is that rather than representing an object by its minimum bounding rectangle (MBR) alone or by pre-processed segmentation into small MBRs, we use the actual shape of the object to maintain the index. This saves significant space for objects with large spatial extents as pre-segmentation into many MBRs is not needed. We show that the query performance of this index is much better than many indexing schemes on synthetic overlapping and also good performance for real-life GIS non-overlapping data sets.