mlsanityData to 7 Oct 2026

A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph

arXiv 2303.06210 ↗First posted 10 Mar 2023cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. These empirical successes urge the need for theoretical results that guarantee the search quality and efficiency of these algorithms. However, there exists a practice-to-theory gap in the graph-based NN-Search algorithms. Current theoretical literature focuses on greedy search on exact near neighbor graph while practitioners use approximate near neighbor graph (ANN-Graph) to reduce the preprocessing time. This work bridges this gap by presenting the theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors. To build this bridge, we leverage several novel tools from computational geometry. Our results provide quantification of the trade-offs associated with the approximation while building a near neighbor graph. We hope our results will open the door for more provable efficient graph-based NN-Search algorithms.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 14 of its 37 references that are in the map. First posted on arXiv 10 Mar 2023.

Builds on

14 of 37 references.

References · 14

  1. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  2. 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 788
  3. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  4. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
  5. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  6. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  7. 2018Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighborscited by 37
  8. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  9. 2019Graph-based Nearest Neighbor Search: From Practice to Theorycited by 19
  10. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  11. 2020Improved Guarantees for k-means++ and k-means++ Parallelcited by 12
  12. 2017Graph-based time-space trade-offs for approximate near neighborscited by 7
2 more
  1. 2021Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?cited by 5
  2. 2017Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Sciencecited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 4; 2025: 5.

10 papers.

  1. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  2. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  3. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  4. 2024RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Searchcited by 12
  5. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  6. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  7. 2023PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Searchcited by 3
  8. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  9. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  10. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0