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.

Visit the LCI Forum page