An Approximate Nearest Neighbor Query Algorithm Based on B^Z-Tree
Hongbo Xu, Nianmin Yao, Qilong Han, Shaobin Cai, Dongpu Sun · 2012
R-tree can achieve better performance in low-dimensional space, but its performance suffers greatly in high-dimensional space. So the reduction of the dimensionality is the key to the problem. Z curve can fill d dimensional space linearly, divide the space into equal-size grids and map points lying in the grids into the linear space. BZ-tree is constructed using Z curve. BZ-tree is a balanced multi-branch tree. BZ-tree has the characteristic of B+-tree and R-tree. In BZ-tree, Z values of the points are the keywords, and all points are stored in leaf nodes, ordered by Z values. Using the reduction of the dimensionality of BZ-tree, the paper presents an approximate k-nearest neighbor query algorithm. According to the test, its running time is shorter than the Brute-Force method and the algorithm based on R-tree, and the quality of the approximate k-nearest neighbors is better.