# Fast Single-Core K-Nearest Neighbor Graph Computation

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

## Key facts

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

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)

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

- [Empirical complexity of comparator-based nearest neighbor descent](https://mlsanity.com/paper/2202.00517/) (2022)

## Abstract (arXiv)

Fast and reliable K-Nearest Neighbor Graph algorithms are more important than ever due to their widespread use in many data processing techniques. This paper presents a runtime optimized C implementation of the heuristic "NN-Descent" algorithm by Wei Dong et al. for the l2-distance metric. Various implementation optimizations are explained which improve performance for low-dimensional as well as high dimensional datasets. Optimizations to speed up the selection of which datapoint pairs to evaluate the distance for are primarily impactful for low-dimensional datasets. A heuristic which exploits the iterative nature of NN-Descent to reorder data in memory is presented which enables better use of locality and thereby improves the runtime. The restriction to the l2-distance metric allows for the use of blocked distance evaluations which significantly increase performance for high dimensional datasets. In combination the optimizations yield an implementation which significantly outperforms a widely used implementation of NN-Descent on all considered datasets. For instance, the runtime on the popular MNIST handwritten digits dataset is halved.