The research on nearest neighbor search algorithm based on vantage point tree

摘要

The nearest neighbor search algorithm is an indispensable part of many image processing algorithms. In order to improve its performance, this paper proposes a similar nearest neighbor search algorithm combining multiple vantage point trees and improved pruning search methods. Firstly, when the vantage point tree is created, the vantage points are selected by selecting the points with the best degree of differentiation; Then, a new method of constructing vantage point forest is proposed to improve the nearest neighbor non-compact problem in the superior sub-tree; Finally, an improved pruning search method is proposed to find similar nearest neighbors, which reduces many unnecessary distance calculations. The experimental results show that the algorithm performance has been greatly improved in the data set size, returned the number of different neighbors, data dimension and the number of building trees.