TY - CONF

T1 - Adaptive estimation for approximate k-nearest-neighbor computations

AU - LeJeune, Daniel

AU - Baraniuk, Richard G.

AU - Heckel, Reinhard

N1 - Funding Information:
We thank the anonymous reviewers for their constructive feedback. DL and RB are partially supported by NSF grants IIS-17-30574 and IIS-18-38177, AFOSR grant FA9550-18-1-0478, ARO grant W911NF-15-1-0316, ONR grants N00014-17-1-2551 and N00014-18-12571, DARPA grant G001534-7500, and DOD Vannevar Bush Faculty Fellowship (NSSEFF) grant N00014-18-1-2047. RH is partially supported by NSF award IIS-1816986.
Publisher Copyright:
© 2019 by the author(s).
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - 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 naïve method.

AB - 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 naïve method.

UR - http://www.scopus.com/inward/record.url?scp=85084973571&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084973571&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85084973571

T2 - 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019

Y2 - 16 April 2019 through 18 April 2019

ER -