mlsanityData to 13 Oct 2026

Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search

arXiv 2402.04713 ↗First posted 7 Feb 2024cs.IR cs.DB cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS). We introduce novel concepts: btextit-monotonic path and Btextit-MSNET, which better capture an actual graph in practical algorithms than existing concepts like MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work. Empirically, we validate the method's effectiveness in accuracy, speed, and memory usage across various datasets, especially in challenging scenarios with out-of-distribution data and hard instances. Our comprehensive study provides deeper insights into optimizing entry points for graph-based ANNS for real-world high-dimensional data applications.

Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 7 Feb 2024.

Builds on

21 of 42 references.

References · 21

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,588
  2. 2022LAION-5B: An open large-scale dataset for training next generation image-text modelscited by 4,141
  3. 2017Billion-scale similarity search with GPUscited by 2,490
  4. 2021LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image-Text Pairscited by 1,548
  5. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 857
  6. 2024The Faiss librarycited by 371
  7. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  8. 2015Practical and Optimal LSH for Angular Distancecited by 105
  9. 2021A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Searchcited by 82
  10. 2022Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Searchcited by 45
  11. 2016Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)cited by 44
  12. 2024Residual Quantization with Implicit Neural Codebookscited by 25
9 more
  1. 2018Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Datacited by 20
  2. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  3. 2019Graph-based Nearest Neighbor Search: From Practice to Theorycited by 19
  4. 2022Uni-Retriever: Towards Learning The Unified Embedding Based Retriever in Bing Sponsored Searchcited by 17
  5. 2016EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graphcited by 15
  6. 2022OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queriescited by 15
  7. 2022Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendationcited by 14
  8. 2023DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertexcited by 7
  9. 2023General and Practical Tuning Method for Off-the-Shelf Graph-Based Index: SISAP Indexing Challenge Report by Team UTokyocited by 3

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Tablecited by 1