# Reducing Nearest Neighbor Training Sets Optimally and Exactly

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 33 references that are in the map.
- First posted on arXiv 4 Feb 2023.

## Builds on (most cited first, 4 of 4)

- [Finding Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2110.06163/) (2021)
- [Coresets for the Nearest-Neighbor Rule](https://mlsanity.com/paper/2002.06650/) (2020)
- [Geometric secluded paths and planar satisfiability](https://mlsanity.com/paper/1902.06471/) (2019)
- [Improved Search of Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2203.03567/) (2022)

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

- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)

## Abstract (arXiv)

In nearest-neighbor classification, a training set P of points in ℝd with given classification is used to classify every point in ℝd: Every point gets the same classification as its nearest neighbor in P. Recently, Eppstein [SOSA'22] developed an algorithm to detect the relevant training points, those points p∈ P, such that P and Psetminusp induce different classifications. We investigate the problem of finding the minimum cardinality reduced training set P'subseteq P such that P and P' induce the same classification. We show that the set of relevant points is such a minimum cardinality reduced training set if P is in general position. Furthermore, we show that finding a minimum cardinality reduced training set for possibly degenerate P is in P for d=1, and NP-complete for d≥ 2.