# Guarantees on Nearest-Neighbor Condensation heuristics

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

## Key facts

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

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

- [Improved Search of Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2203.03567/) (2022)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)

## Abstract (arXiv)

The problem of nearest-neighbor (NN) condensation aims to reduce the size of a training set of a nearest-neighbor classifier while maintaining its classification accuracy. Although many condensation techniques have been proposed, few bounds have been proved on the amount of reduction achieved. In this paper, we present one of the first theoretical results for practical NN condensation algorithms. We propose two condensation algorithms, called RSS and VSS, along with provable upper-bounds on the size of their selected subsets. Additionally, we shed light on the selection size of two other state-of-the-art algorithms, called MSS and FCNN, and compare them to the new algorithms.