mlsanityData to 7 Oct 2026

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

arXiv 1712.02369 ↗First posted 6 Dec 2017math.ST stat.ML stat.THcited by 10

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 3; 2024: 0; 2025: 1; 2026: 2.

10 papers.

  1. 2021Under-bagging Nearest Neighbors for Imbalanced Classificationcited by 3
  2. 2025Concentration and excess risk bounds for imbalanced classification with synthetic oversamplingcited by 3
  3. 2022Benefit of Interpolation in Nearest Neighbor Algorithmscited by 1
  4. 2022On Error and Compression Rates for Prototype Rulescited by 1
  5. 2023Fast and Multiphase Rates for Nearest Neighbor Classifierscited by 1
  6. 2023On Rate-Optimal Partitioning Classification from Observable and from Privatised Datacited by 1
  7. 2022Enhanced Nearest Neighbor Classification for Crowdsourcingcited by 0
  8. 2023Weighted Distance Nearest Neighbor Condensingcited by 0
  9. 2026On public and private binary classification with metric space valued predictorscited by 0
  10. 2026Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margincited by 0