Packed R-trees Using Fractals
Abstract
We propose a new packing technique for R-trees for static databases. Given a
collection of rectangles, we sort them and we build the Rtree bottom-up.
There are several ways to sort the rectangles; the innovation of this work
is the use of fractals, and specifically the hilbert curve, to achieve
better ordering of the rectangles and eventually better packing. We
proposed and implemented several variations and performed experiments on
synthetic, as well as real data (a TIGER file from the U.S. Bureau of Census).
The winning variation ('2D-c') was the one that sorts the rectangles according
to the hilbert value of the center. This variation consistently outperforms
the R*-trees [3], Guttman's R-trees [13], as well as the packing method of
Roussopoulos and Leifker [24]. The performance gain of the our method seems
to increase with the skeweness of the data distribution; specifically, on
the (highly skewed) TIGER dataset, it achieves up to 38% improvement in
response time over the best known R-tree variant and up to 58% over the
older packing algorithm.
(Also cross-referenced as UMIACS-TR-92-133)