带聚类的Hilbert R-树建树算法

CLUSTERING METHOD USED IN HILBERT R-TREE BUILDING

本文提出了一种新的建立在一维聚类上的建树方法。该算法改变了原来Hillbert R-树建树方法中的机械填充方式,通过在数据的Hilbert值集合中进行的聚类而对叶子节点中的数据进行优化组合从而得到了更小的叶子节点,提高了检索的效率。实验表明,特别对于分布不均匀的数据,该算法在有限增加计算复杂度的前提下可以大大提高检索效率。

In this article, we propose a new method of building the Hilbert R-tree based on clustering. The new algorithm outperforms the former one of mechanical filling and realizes optimized combination of data in leaf nodes by clustering in their Hilbert value sets. In this way, we can get smaller leaf nodes and improve the efficiency of retrieval. Experiments on both simulated and real data show that under the condition of computing complexity increased to a limited extent, this algorithm can greatly reduce the search cost, especially for data sets with skewed distribution.