Adaptive Estimation for Approximate $k$-Nearest-Neighbor Computations

Daniel LeJeune, Reinhard Heckel, Richard Baraniuk
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3099-3107, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-lejeune19a, title = {Adaptive Estimation for Approximate $k$-Nearest-Neighbor Computations}, author = {LeJeune, Daniel and Heckel, Reinhard and Baraniuk, Richard}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {3099--3107}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/lejeune19a/lejeune19a.pdf}, url = {https://proceedings.mlr.press/v89/lejeune19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Adaptive Estimation for Approximate $k$-Nearest-Neighbor Computations %A Daniel LeJeune %A Reinhard Heckel %A Richard Baraniuk %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-lejeune19a %I PMLR %P 3099--3107 %U https://proceedings.mlr.press/v89/lejeune19a.html %V 89 %X 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.
APA
LeJeune, D., Heckel, R. & Baraniuk, R.. (2019). Adaptive Estimation for Approximate $k$-Nearest-Neighbor Computations. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3099-3107 Available from https://proceedings.mlr.press/v89/lejeune19a.html.

Related Material