Fast Nearest Neighbor Search In The Hamming Space

Nearest neighbor search is a fundamental problem in machine learning and data mining,and there are many related applications in the real world,such as similar image search and image classification based on nearest neighbor search.Many works about nearest neighbor search appear in the past few years.Algorithms on nearest neighbor search are mainly linear scan,tree structure,neighborhood graph,hashing and inverted index approach.Linear scan approach is a basic method for nearest neighbor search,which visits all the data points in the database to retrieve the nearest neighbors.Tree-structured index method recursively partitions the space and constructs a tree-structured index for nearest neighbor search.Another nearest neighbor search method is based on the neighborhood graph among the search database.Hashing algorithms map data from original space to the Hamming space and turn the search problem into the Hamming space.Inverted index,which is built by clustering algorithm,can be used in nearest neighbor search to improve the efficiency.In [1],a new approximate NN search algorithm is presented.With the concept of bridge vectors which correspond to the cluster centers in Product Quantization [2] and the augmented neighborhood graph,it is possible to adopt an extract-on-demand strategy on the online querying stage to search with priority.Recent years have witnessed growing interests in computing compact binary codes and binary visual descriptors to alleviate the heavy computational costs in large-scale visual research.However,it is still computationally expensive to linearly scan the large-scale databases for nearest neighbor(NN)search.This paper generalizes the algorithm in [1] to the Hamming space with an alternative version of k-means clustering.Our approach achieves competitive performance compared to the state-of-the-art methods,i.e.,MIH [3] and FLANN [4],in the aspects of search precision,accessed data volume and average querying time.