High-dimensional indexing algorithm based on the hyperplane tree-structure

“Adaptive Cluster Distance Bounding” could obtain tighter distance boundaries between the query and clusters, but this method suffers large amount of distance boundary computations and can´t take both filtration capacity and CPU performance as the number of clusters increases, and doesn´t yet provide effective pruning mechanisms inside the candidate clusters. In this paper, a new indexing method is provided, called TreeHB, to improve the performance of nearest-neighbor search, which is based on two improvements of existing hyperplane method. Firstly, we divide clusters with hierarchic methods, and manage the clustering results with a tree structure, which can reduce the amount of computation and the CPU cost under the precondition of ensuring filtering capabilities. Secondly, a new pruning algorithm is designed to reject the irrelevant points further in the candidate clusters and reduce the IO cost. It turns out that the new approach outperforms the original hyperplane method and other popular high-dimensional indexing methods.