Graph-Based Nearest-Neighbor Search with Recall Guarantees Using Graph Spanners
cs.DB, cs.CL, cs.IR, cs.LG
Submitted: 2026-07-02
Updated: 2026-11-11
Code: https://github.com/ming-afk/recall_certify_hnsw
Terminology
Sources
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
- A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification
- The Faiss library
- PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs
- $\pi^{*}_{0.6}$: a VLA That Learns From Experience
- CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
- Improving Biomedical Entity Linking with Retrieval-enhanced Learning
- Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints
- Proxy-based Zero-Shot Entity Linking by Effective Candidate Retrieval
- Tao: A Learning Framework for Adaptive Nearest Neighbor Search using Static Features Only
- Distribution-Aware Exploration for Adaptive HNSW Search
Related papers
- Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs