Research On Approximate Nearest Neighbor Search Methods Based On Approximate K-NN Graph For Image Retrieval

Nearest neighbor search(NNS)as a fundamental issue generally arises from a wide range of subjects,such as database,machine learning,computer vision,and informa-tion retrieval.The nearest neighbor search problem can be simply defined as follows.Given a query vector,and n candidates that are under the same dimensionality.It is required to return sample(s)for the query that are closest to it according to certain metric.In lots of real-world applications,get exact nearest neighbor(s)usu-ally needs expensive time and space cost.And approximate nearest neighbor search significantly reduces the cost of space and time at the expense of lowering certain ac-curacy.The practicality of the approximate nearest neighbor search makes it arising amount of cencentration and plenty of algorithms have been proposed successively,including space partition based,hashing based,quantization based and neighbor-hood graph based algorithms.However,there are not sublinear time complexity approximate nearest neighbor search algorithms in all scenes.In the era of big data,designing a higher quality,efficient,approximate nearest neighbor search algorithm has important theoretical significance and practical value.The approximate nearest neighbor search algorithm based on(approximate)k-nearest neighbor graph(k-NN graph)is the current mainstream algorithm and generally includes two steps.One is to construct the k-NN graph with the candidate vectors in the offline period,and the other is to use a certain search strategy to return query results based on k-NN graph.The quality of the k-NN graph and search strategy greatly affect the effectiveness and efficiency of the algorithm.This paper improves the construction of the k-NN graph and the hill-climbing algorithm(GNN'S).The main results are:(1)Based on the observation that hill-climbing search algorithm has redundant cal-culations and slow convergence speeds,an enhanced hill-climbing search(E-GNNS)algorithm is proposed.In each round of iterations,not only the first sample,but the first k sample are expanded on the k-NN graph.Experiments show that the E-GNNS algorithm has achieved significant improvement in search efficiency and average recall.(2)In the selection of seeds for hill-climbing,an inverted index based on RVQ is used to get candidate seeds,which replaces the random seeds of the original method.Experiments show that under the support of this strategy,the E-GNNS algorithm's average recall is boosted more than 10%with similar search time across two datasets.(3)In order to overcome the disadvantages of low efficiency and serious memory consumption in constructing k-NN graph,a light-weight construction method based on 2-M tree is proposed.Experiments show that this method can significantly reduce the time and memory consumption of k-NN graph construction without sacrificing the search efficiency and quality in the later period.