# Fast and Bayes-consistent nearest neighbors

arXiv: https://arxiv.org/abs/1910.05270 · HTML: https://mlsanity.com/paper/1910.05270/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2019.

## Built on by (most cited first, 1 of 1)

- [One-Layer Transformer Provably Learns Multiclass One-Nearest Neighbor in Context](https://mlsanity.com/paper/2609.01311/) (2026)

## Abstract (arXiv)

Research on nearest-neighbor methods tends to focus somewhat dichotomously either on the statistical or the computational aspects -- either on, say, Bayes consistency and rates of convergence or on techniques for speeding up the proximity search. This paper aims at bridging these realms: to reap the advantages of fast evaluation time while maintaining Bayes consistency, and further without sacrificing too much in the risk decay rate. We combine the locality-sensitive hashing (LSH) technique with a novel missing-mass argument to obtain a fast and Bayes-consistent classifier. Our algorithm's prediction runtime compares favorably against state of the art approximate NN methods, while maintaining Bayes-consistency and attaining rates comparable to minimax. On samples of size n in Rd, our pre-processing phase has runtime O(d n log n), while the evaluation phase has runtime O(dlog n) per query point.