摘要: Z树能够高效地处理对高维度数据集的矩形区域查询和最邻近搜索。它按照节点的形状变化量优化数据的插入位置,使节点形状趋于合理。文章给出了一个新的无重叠分裂算法,减少超级节点的产生。引入了动态剪枝和重新插入策略,压缩超级节点的数量和体积。提出了矩形节点的球形化方法和最优子树搜索算法。实验表明Z树的矩形区域查询和最邻近搜索的效率远远高于X树和SR树。
关键词:
索引,
高维度数据,
矩形区域查询,
最近邻域搜索
Abstract: The Z Tree supports the searches of rectangle area and the nearest-neighbors (NN) effectively for high-dimensional data sets. The shape variable of nodes is taken into account to optimize the sub-tree’s selection for new data insertion. A new overlap-free split algorithm is proposed to avoid the generation of supernodes. A dynamic pruning and reinsertion policy is used to reduce the number and volume of supernodes. A novel method is introduced to convert a rectangle tree to a sphere tree to speed up the NN search. A new efficient algorithm of the NN search is proposed based on the optimization of search order among sub-trees. The experiments show that the Z Tree is more efficient than X Tree and SR Tree for high-dimensional data.
Key words:
index,
high-dimensional data,
rectangle area search,
nearest-neighbor search
中图分类号:
张 强;赵 政. Z树:一个高维度的数据索引结构[J]. 计算机工程, 2007, 33(15): 49-51.
ZHANG Qiang; ZHAO Zheng. Z Tree: An Index Structure for High-dimensional Data[J]. Computer Engineering, 2007, 33(15): 49-51.