# Weighted Distance Nearest Neighbor Condensing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 24 Oct 2023.

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)
- [Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions](https://mlsanity.com/paper/1705.08184/) (2017)
- [Guarantees on Nearest-Neighbor Condensation heuristics](https://mlsanity.com/paper/1904.12142/) (2019)
- [Social Distancing is Good for Points too!](https://mlsanity.com/paper/2006.15650/) (2020)
- [Classification in asymmetric spaces via sample compression](https://mlsanity.com/paper/1909.09969/) (2019)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)

## Abstract (arXiv)

The problem of nearest neighbor condensing has enjoyed a long history of study, both in its theoretical and practical aspects. In this paper, we introduce the problem of weighted distance nearest neighbor condensing, where one assigns weights to each point of the condensed set, and then new points are labeled based on their weighted distance nearest neighbor in the condensed set. We study the theoretical properties of this new model, and show that it can produce dramatically better condensing than the standard nearest neighbor rule, yet is characterized by generalization bounds almost identical to the latter. We then suggest a condensing heuristic for our new problem. We demonstrate Bayes consistency for this heuristic, and also show promising empirical results.