Indexing for Dynamic Abstract Regions
Joxan Jaffar, Roland H.C. Yap, Kenny Q. Zhu
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.