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)