# Finding Relevant Points for Nearest-Neighbor Classification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 44 references that are in the map.
- First posted on arXiv 12 Oct 2021.

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

- [On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic](https://mlsanity.com/paper/1812.00901/) (2018)

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

- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [Improved Search of Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2203.03567/) (2022)
- [Reducing Nearest Neighbor Training Sets Optimally and Exactly](https://mlsanity.com/paper/2302.02132/) (2023)

## Abstract (arXiv)

In nearest-neighbor classification problems, a set of d-dimensional training points are given, each with a known classification, and are used to infer unknown classifications of other points by using the same classification as the nearest training point. A training point is relevant if its omission from the training set would change the outcome of some of these inferences. We provide a simple algorithm for thinning a training set down to its subset of relevant points, using as subroutines algorithms for finding the minimum spanning tree of a set of points and for finding the extreme points (convex hull vertices) of a set of points. The time bounds for our algorithm, in any constant dimension d≥ 3, improve on a previous algorithm for the same problem by Clarkson (FOCS 1994).