FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
Marius Muja, David G. Lowe · International Conference on Computer Vision Theory and Applications · 2009
nearest-neighbors search, randomized kd-trees, hierarchical k-means tree, clustering. 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. 1
Cited by 2,575 works. doi:10.5220/0001787803310340
Authors
References
- Distinctive Image Features from Scale-Invariant Keypoints
- Video Google: a text retrieval approach to object matching in videos
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- Scalable Recognition with a Vocabulary Tree
- 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Shape indexing using approximate nearest-neighbour search in high-dimensional spaces
- Object retrieval with large vocabularies and fast spatial matching
- A Branch and Bound Algorithm for Computing k-Nearest Neighbors
- Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions