Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration
By Marius Muja
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. The question we
try to answer is: ``What is the fastest approximate nearest-neighbor algorithm
for my data?'' We present a system that 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.
This is joint work with David Lowe.