Adaptive estimation for approximate k-nearest-neighbor computations

Daniel LeJeune, Richard G. Baraniuk, Reinhard Heckel

Research output: Contribution to conferencePaper

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

Original languageEnglish (US)
StatePublished - 2020
Event22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan
Duration: Apr 16 2019Apr 18 2019

Other

Other22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019
CountryJapan
CityNaha
Period4/16/194/18/19

ASJC Scopus subject areas

  • Artificial Intelligence
  • Statistics and Probability

Fingerprint Dive into the research topics of 'Adaptive estimation for approximate k-nearest-neighbor computations'. Together they form a unique fingerprint.

  • Cite this

    LeJeune, D., Baraniuk, R. G., & Heckel, R. (2020). Adaptive estimation for approximate k-nearest-neighbor computations. Paper presented at 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, Naha, Japan.