Hilbert R-tree: An improved Rtree using fractals
Hilbert R-tree: An improved Rtree using fractals
Files
Publication or External Link
Date
1998-10-15
Authors
Kamel, Ibrahim
Faloutsos, Christos
Advisor
Citation
DRUM DOI
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
R*tree. 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)