Algorithms often carry out equally many computations for "easy" and "hard" problem instances. In particular, algorithms for finding nearest neighbors typically have the same running time regardless of the particular problem instance. In this paper, we consider the approximate $k$-nearest-neighbor problem, which is the problem of finding a subset of O(k) points in a given set of points that contains the set of $k$ nearest neighbors of a given query point. We propose an algorithm based on adaptively estimating the distances, and show that it is essentially optimal out of algorithms that are only allowed to adaptively estimate distances. We then demonstrate both theoretically and experimentally that the algorithm can achieve significant speedups relative to the naive method.
展开▼
机译：对于“容易”和“困难”的问题实例，算法通常执行同样多的计算。尤其是，用于查找最近邻居的算法通常具有相同的运行时间，而不管特定的问题实例如何。在本文中，我们考虑了近似的$ k $-最近邻问题，即在给定点集中找到O（k）个点的子集的问题，该子集包含给定点的$ k $最近邻。查询点。我们提出了一种基于自适应估计距离的算法，并表明它在仅允许自适应估计距离的算法中本质上是最优的。然后，我们在理论上和实验上都证明了该算法相对于朴素的方法可以实现明显的加速。
展开▼
