# Graph-Based Nearest-Neighbor Search without the Spread

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 6 Feb 2026.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits](https://mlsanity.com/paper/2405.18680/) (2024)
- [Approximate Greedy Clustering and Distance Selection for Graph Metrics](https://mlsanity.com/paper/1507.01555/) (2015)
- [Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness](https://mlsanity.com/paper/2507.14060/) (2025)
- [Efficiently Constructing Sparse Navigable Graphs](https://mlsanity.com/paper/2507.13296/) (2025)
- [The Road to the Closest Point is Paved by Good Neighbors](https://mlsanity.com/paper/2509.23966/) (2025)

## Abstract (arXiv)

renewcommandReℝRecent work showed how to construct nearest-neighbor graphs of linear size, on a given set P of n points in Red, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in n, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in n.