# A True O(n logn)  Algorithm for the All-k-Nearest-Neighbors Problem

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2019.

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

- [Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity](https://mlsanity.com/paper/2203.08027/) (2022)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)

## Abstract (arXiv)

In this paper we examined an algorithm for the All-k-Nearest-Neighbor problem proposed in 1980s, which was claimed to have an O(nlogn) upper bound on the running time. We find the algorithm actually exceeds the so claimed upper bound, and prove that it has an Omega(n2) lower bound on the time complexity. Besides, we propose a new algorithm that truly achieves the O(nlogn) bound. Detailed and rigorous theoretical proofs are provided to show the proposed algorithm runs exactly in O(nlogn) time.