Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration
Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration
复制标题
DOI：
10.5220/0001787803310340
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Marius Muja;D. Lowe
中科院分区：
文献类型：
--
作者：
Marius Muja;D. Lowe
对于许多计算机视觉问题，最耗时的部分包括高维空间中的最近邻匹配。没有已知的精确算法来解决这些高维问题，比线性搜索更快。已知近似算法提供大的加速比，而仅在精度上有微小的损失，但是许多这样的算法已经在针对任何给定的问题选择算法及其参数方面仅具有最小的指导。在本文中，我们描述了一个系统，回答这个问题，“什么是最快的近似最近邻算法我的数据？”我们的系统将采用任何给定的数据集和所需的精度，并使用这些来自动确定最佳算法和参数值。我们还描述了一个新的算法，适用于优先级搜索分层k-均值树，我们已经发现，提供了最好的已知性能在许多数据集上。在测试了一系列替代方案后，我们发现多个随机k-d树为其他数据集提供了最佳性能。我们正在发布实现这些方法的公共领域代码。这个库提供了一个数量级的改进，在查询时间超过最好的以前可用的软件，并提供完全自动化的参数选择。
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.