# Achieving the time of 1-NN, but the accuracy of k-NN

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2017.

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

- [Concentration and excess risk bounds for imbalanced classification with synthetic oversampling](https://mlsanity.com/paper/2510.20472/) (2025)
- [Under-bagging Nearest Neighbors for Imbalanced Classification](https://mlsanity.com/paper/2109.00531/) (2021)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [On Rate-Optimal Partitioning Classification from Observable and from Privatised Data](https://mlsanity.com/paper/2312.14889/) (2023)
- [Enhanced Nearest Neighbor Classification for Crowdsourcing](https://mlsanity.com/paper/2203.00781/) (2022)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [On public and private binary classification with metric space valued predictors](https://mlsanity.com/paper/2605.31184/) (2026)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

We propose a simple approach which, given distributed computing resources, can nearly achieve the accuracy of k-NN prediction, while matching (or improving) the faster prediction time of 1-NN. The approach consists of aggregating denoised 1-NN predictors over a small number of distributed subsamples. We show, both theoretically and experimentally, that small subsample sizes suffice to attain similar performance as k-NN, without sacrificing the computational efficiency of 1-NN.