# The Road to the Closest Point is Paved by Good Neighbors

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2025.

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

- [Graph-Based Nearest-Neighbor Search without the Spread](https://mlsanity.com/paper/2602.06633/) (2026)

## Abstract (arXiv)

renewcommandReℝGiven a set P of n points in Red, and a parameter varepsilon ∈ (0,1), we present a new construction of a directed graph G, of size O(n/varepsilond), such that (1+varepsilon)-ANN queries can be answered by performing a greedy walk on G, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is O( varepsilon-d log Psi), where Psi is the spread of P. The new construction is surprisingly simple and should be practical.