FLANN: Fast Library for Approximate Nearest Neighbor Matching
(Marius Muja and David Lowe)
The most time consuming part of performing object recognition in large databases is to identify the closest matches for high-dimensional vectors among millions of similar vectors. There are typically no exact algorithms for solving this problem faster than linear search, so it is necessary to use approximate algorithms that sometimes return a slightly less than optimal answer but can be thousands of times faster. We have implemented the best known previous algorithms for approximate nearest neighbor search and developed our own improved methods. Different algorithms are the best choices for different problems, so we have also developed an automated algorithm configuration system that selects the best algorithm and parameters for particular data.
FLANN home page