# Empirical complexity of comparator-based nearest neighbor descent

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 30 Jan 2022.

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Comparison Based Nearest Neighbor Search](https://mlsanity.com/paper/1704.01460/) (2017)
- [Partitioned K-nearest neighbor local depth for scalable comparison-based learning](https://mlsanity.com/paper/2108.08864/) (2021)
- [Fast Single-Core K-Nearest Neighbor Graph Computation](https://mlsanity.com/paper/2112.06630/) (2021)

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

- [Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction](https://mlsanity.com/paper/2203.12997/) (2022)
- [Scalable network reconstruction in subquadratic time](https://mlsanity.com/paper/2401.01404/) (2024)

## Abstract (arXiv)

A Java parallel streams implementation of the K-nearest neighbor descent algorithm is presented using a natural statistical termination criterion. Input data consist of a set S of n objects of type V, and a Function<V, Comparator<V>>, which enables any x ∈ S to decide which of y, z ∈ Ssetminusx is more similar to x. Experiments with the Kullback-Leibler divergence Comparator support the prediction that the number of rounds of K-nearest neighbor updates need not exceed twice the diameter of the undirected version of a random regular out-degree K digraph on n vertices. Overall complexity was O(n K2 logK(n)) in the class of examples studied. When objects are sampled uniformly from a d-dimensional simplex, accuracy of the K-nearest neighbor approximation is high up to d = 20, but declines in higher dimensions, as theory would predict.