Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration

By Marius Muja, David G. Lowe. 2009

3,299 citations recorded by the source corpus.

For many computer vision problems, the most time consuming component consists of nearest neighbor matching in high-dimensional spaces. There are no known exact algorithms for solving these high-dimensional problems that are faster than linear search. Approximate algorithms are known to provide large speedups with only minor loss in accuracy, but many such algorithms have been published with only minimal guidance on selecting an algorithm and its parameters for any given problem. In this paper, we describe a system that answers the question, “What is the fastest approximate nearest-neighbor algorithm for my data?” Our system will take any given dataset and desired degree of precision and use these to automatically determine the best algorithm and parameter values. We also describe a new algorithm that applies priority search on hierarchical k-means trees, which we have found to provide the best known performance on many datasets. After testing a range of alternatives, we have found that multiple randomized k-d trees provide the best performance for other datasets. We are releasing public domain code that implements these approaches. This library provides about one order of magnitude improvement in query time over the best previously available software and provides fully automated parameter selection.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Trevor Darrell
  2. Luc Van Gool
  3. Yoshua Bengio
  4. Andrew Zisserman
  5. Cordelia Schmid
  6. Quoc V. Le
  7. Bernt Schiele
  8. Mohit Bansal

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Andrew Zisserman
  4. Ming-Hsuan Yang
  5. Trevor Darrell
  6. Yi Yang
  7. Xiaogang Wang
  8. Jitendra Malik

In Information Retrieval & Search

  1. Herv'e J'egou
  2. Ondřej Chum
  3. Jingdong Wang
  4. Matthijs Douze
  5. Qi Tian
  6. Yannis Avrithis
  7. Cordelia Schmid
  8. Giorgos Tolias

In Signal Processing

  1. Kristen Grauman
  2. Andrea Vedaldi
  3. Jingdong Wang
  4. Ivan Laptev
  5. Cordelia Schmid
  6. Josef Sivic
  7. Herv'e J'egou
  8. Jiri Matas

Citations in the corpus