Query-driven iterated neighborhood graph search for scalable visual indexing

In this paper, we address the approximate nearest neighbor (ANN) search problem over large scale visual descriptors. We investigate a simple but very effective approach, neighborhood graph (NG) search, which conducts the local search by expanding neighborhoods with a best-first manner. Expanding neighborhood makes it efficient to locate the descriptors with high probability being true NNs. However, it suffers from the local characteristics, and often gets sub-optimal solutions, or conducts exhaustive and continuous neighborhood expansion to find better solutions which deteriorates the query efficiency.

We propose a query-driven iterated neighborhood graph search approach to improve the performance. We follow the iterated local search (ILS) strategy widely-used for combinatorial and discrete optimization in operation research, and handle the key issue in applying ILS for neighborhood graph search, Perturbation, which generates a new pivot to restart a local search. The key novelties lie in two-fold: (1) defining the local solution of ANN search over neighborhood graph; (2) presenting a query and search history driven perturbation scheme to generate pivots to restart a new local search. The main benefit from them is avoiding unnecessary neighborhood expansion and hence more efficiently finding true NNs. Experimental results on large scale SIFT indexing and similar image search with tiny images show that our approach performs much better than previous state-of-the-art ANN search approaches.