Hilbert R-tree: An Improved R-tree Using Fractals

We propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in R-trees. This is done by proposing an ordering on the R-tree nodes. This ordering has to be 'good', in the sense that it should group 'similar ' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19] we have chosen the so-called '2D-c ' method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a well-de ned set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. To the contrary, the R-tree has no control over the space utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Hilbert R-tree. Our experiments show that the '2-to-3 ' split policy provides a compromise between the insertion complexity and the search cost, giving up to 28 % savings over the R tree [3] on real data.