On packing R-trees

We propose new R-tree packing techniques for static databases. Given a collection of rectangles, we sort them and build the R-tree 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 (TIGER files 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 packing method of Roussopou- 10S and Leifker [21], as well as other R-tree variants. 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 58% improvement in response time over the older packing algorithm and 36yo over the best known R-tree variant. We also, introduce an analytical formula to compute the average response time of a range query as a function of the geometric characteristics of the R-tree.