mlsanityData to 7 Oct 2026

Graph-Based Nearest-Neighbor Search without the Spread

arXiv 2602.06633 ↗First posted 6 Feb 2026cs.CG cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

8 of 27 references.

References · 8

  1. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  2. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
  3. 2023ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithmscited by 24
  4. 2024Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limitscited by 7
  5. 2015Approximate Greedy Clustering and Distance Selection for Graph Metricscited by 3
  6. 2025Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardnesscited by 2
  7. 2025Efficiently Constructing Sparse Navigable Graphscited by 1
  8. 2025The Road to the Closest Point is Paved by Good Neighborscited by 1

Built on by

Not cited yet.