An Approximate Nearest Neighbor Query Algorithm Based on B^Z-Tree

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. B^Z-tree is constructed using Z curve. B^Z-tree is a balanced multi-branch tree. B^Z-tree has the characteristic of B⁺-tree and R-tree. In B^Z-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 B^Z-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.