Hilbert R-tree: An improved Rtree using fractals

Abstract

We propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to pack rectangles into the Entree nodes according to a linear ordering as opposed to the more complex heuristics used in the Rtree. This ordering has to be 'good', in the sense that it should cluster 'similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Among the orderings we tried, the '2bc' method, the one that uses the (2d) Filbert value of the center of the rectangles, gives the best results. For a static database, the proposed ordering achieves superior packing, outperforming older packing methods [25], and the best dynamic method (R-trees [3]). The savings are as high as 36% on real data. Moreover, we introduce a dynamic variation, the Eilbc7t R-tree: Given the ordering, every node has a well-defined set of sibling nodes; thus, we can use splitting algorithms that are similar to the deferred splitting of the B*-trees. By adjusting the split policy, the Filbert R-tree can achieve as high utilization as desired. To the contrary, the R*-tree has no control over the utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Filbert R-tree. Our experiments show that a '2-to-3' split policy achieves good results, consistently outperforming the best competitor (R*-trees), with up to 28% savings on real data. (Also cross-referenced as UMIACS-TR-93-12)