On packing R-trees
On packing R-trees
复制标题
DOI：
10.1145/170088.170403
复制
发表时间：
1993-12
期刊：
影响因子：
--
通讯作者：
I. Kamel;C. Faloutsos
中科院分区：
文献类型：
--
作者：
I. Kamel;C. Faloutsos
我们为静态数据库提供了新的R-Tree包装技术。鉴于一系列的直角，我们对它们进行分类，然后构建R-Tree自下而上。有几种分类矩形的方法；这项工作的创新是使用分形，而特定（CID：12）则是希尔伯特曲线的cally，以实现更好的矩形排序，并最终更好地包装。我们提出并实施了几种变体，并进行了有关合成和真实数据的实验（Tiger（CID：12）来自美国人口普查局）。获胜的变化（“ 2D-C”）是根据中心的希尔伯特价值对矩形进行分类的变化。这种变化始终优于Roussopoulos和Leifker [24]以及其他R-Tree变体的包装方法。我们方法的性能增益似乎随数据分布的偏差而增加。特定（CID：12）Cally，在（高度偏斜）的老虎数据集上，它的响应时间比较旧的包装算法的响应时间高达58％，而最著名的R-Tree变体的响应时间则达到了36％。我们还引入一个分析公式，以计算范围查询的平均响应时间，这是R-Tree几何特征的函数。
We propose new R-tree packing techniques for static databases. Given a collection of rect-angles, we sort them and we 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 speci(cid:12)cally 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 (cid:12)les 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 Roussopoulos and Leifker [24], as well as other R-tree variants. The performance gain of the our method seems to increase with the skeweness of the data distribution; speci(cid:12)cally, on the (highly skewed) TIGER dataset, it achieves up to 58% improvement in response time over the older packing algorithm and 36% 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.