Research map / Learning theory and algorithms / Prediction and decision losses
Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use slow rather than fast preprocessing | DiskANN · Constructed hard instance | steps to exact nearest neighbor: 10% of the vertex set -> 2 steps | Helped |
| Evaluate graph ANN search on constructed adversarial instances | DiskANN fast preprocessing · Constructed hard instances | Recall@5: 0.0 | Hurt |
| Use fast preprocessing rather than slow preprocessing | DiskANN · Constructed hard instance | steps before encountering any top 5 nearest neighbor: 2 steps -> at least 0.1 n steps | Hurt |
| Evaluate NSG on constructed adversarial instances | NSG · Constructed hard instances | Recall@5: 0.27 | Hurt |
| Evaluate HNSW on constructed adversarial instances | HNSW · Constructed hard instances | Recall@5: 0.1 | Hurt |
| Use slow preprocessing with bounded doubling dimension | DiskANN · Bounded-doubling-dimension data | approximation ratio: \left(\frac{\alpha+1}{\alpha-1}+\epsilon\right) | Helped |
| Use slow preprocessing with bounded doubling dimension | DiskANN · Bounded-doubling-dimension data | query steps: O\left(\log_{\alpha}\frac{\Delta}{(\alpha-1)\epsilon}\right) | Helped |
| Set the search queue length below 10% of the dataset size | Graph-based ANN algorithms on constructed hard instances · Constructed hard instances | Recall@5: 10% | Hurt |
Closest papers by meaning
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.91)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.90)
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.88)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.88)
- Approximate Nearest Neighbor Search with Window Filters (ICML 2024 · similarity 0.87)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.