Z Tree: An Index Structure for High-dimensional Data
Zheng Zhao · Jisuanji gongcheng · 2007
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.