Compacting Discriminator Information for Spatial Trees

Sitzmann, I. and Stuckey, P.J.

Cache-conscious behaviour of data structures becomes more important as memory sizes increase and whole databases fit into main memory For spatial data, R-trees, originally designed for disk-based data, can be adopted for in-memory applications. In this paper we will investigate how the small amount of space in an in-memory R-tree node can be used better to make R-trees more cache-conscious. We observe that many entries share sides with their parents, and introduce the partial R-tree which only stores information that is not given by the parent node. Our experiments showed that ht partial R-tree shows up to 30 per cent better performance than the traditional R-tree. We also investigated if we could improve the search performance by storing more descriptive information instead of the standard minimum bounding box without decreasing the fanout of the R-tree. The partial static O-tree is based on the O-tree, but stores only the most important part of the information of an O-tree box. Experiments showed that this approach reduces the search time for line data by up to 60 per cent.

Cite as: Sitzmann, I. and Stuckey, P.J. (2002). Compacting Discriminator Information for Spatial Trees. In Proc. Thirteenth Australasian Database Conference (ADC2002), Melbourne, Australia. CRPIT, 5. Zhou, X., Ed. ACS. 167-176.

(from crpit.com) (local if available)