Effective Decompositioning of Complex Spatial Objects into Intervals

H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz (Germany)


Relational Indexing, Spatial Objects, Decompositioning.


In order to guarantee efficient query processing together with industrial strength, spatial index structures have to be integrated into fully-fledged object-relational database management systems (ORDBMSs). A promising way to cope with spatial data can be found somewhere in between replicating and non-replicating spatial index structures. In this paper, we use the concept of gray intervals which helps to range between these two extremes. Based on the gray in tervals, we introduce a cost-based decomposition method for accelerating the Relational Interval Tree (RI-tree). Our approach uses compression algorithms for the effective storage of the decomposed spatial objects. The experimen tal evaluation on real-world test data points out that our new concept outperforms the RI-tree by up to two orders of magnitude with respect to overall query response time and secondary storage space.

Important Links:

Go Back