# Improved Search of Relevant Points for Nearest-Neighbor Classification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 7 Mar 2022.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning](https://mlsanity.com/paper/1803.04765/) (2018)
- [On the Robustness of Deep K-Nearest Neighbors](https://mlsanity.com/paper/1903.08333/) (2019)
- [Adversarial Training with Voronoi Constraints](https://mlsanity.com/paper/1905.01019/) (2019)
- [Optimal Approximate Polytope Membership](https://mlsanity.com/paper/1612.01696/) (2016)
- [Finding Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2110.06163/) (2021)
- [Approximate Polytope Membership Queries](https://mlsanity.com/paper/1604.01183/) (2016)
- [Guarantees on Nearest-Neighbor Condensation heuristics](https://mlsanity.com/paper/1904.12142/) (2019)
- [Coresets for the Nearest-Neighbor Rule](https://mlsanity.com/paper/2002.06650/) (2020)
- [Social Distancing is Good for Points too!](https://mlsanity.com/paper/2006.15650/) (2020)

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

- [Reducing Nearest Neighbor Training Sets Optimally and Exactly](https://mlsanity.com/paper/2302.02132/) (2023)

## Abstract (arXiv)

Given a training set P subset ℝd, the nearest-neighbor classifier assigns any query point q ∈ ℝd to the class of its closest point in P. To answer these classification queries, some training points are more relevant than others. We say a training point is relevant if its omission from the training set could induce the misclassification of some query point in ℝd. These relevant points are commonly known as border points, as they define the boundaries of the Voronoi diagram of P that separate points of different classes. Being able to compute this set of points efficiently is crucial to reduce the size of the training set without affecting the accuracy of the nearest-neighbor classifier. Improving over a decades-long result by Clarkson, in a recent paper by Eppstein an output-sensitive algorithm was proposed to find the set of border points of P in O( n2 + nk2 ) time, where k is the size of such set. In this paper, we improve this algorithm to have time complexity equal to O( nk2 ) by proving that the first steps of their algorithm, which require O( n2 ) time, are unnecessary.