Research map / Learning theory and algorithms / Prediction and decision losses
A Bi-metric Framework for Efficient Nearest Neighbor Search
Haike Xu, Sandeep Silwal, Piotr Indyk
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| run graph search with expensive metric D on a graph index built with cheap metric d, seeded from the cheap-metric top-Q/2 results, instead of retrieve-then-rerank | DiskANN bi-metric search · HotpotQA, bge-micro-v2 + SFR-Embedding-Mistral | calls to D for matched NDCG@10: 8000 -> <2000 calls | Improved |
| bi-metric search with Gemini-2.0-Flash as the expensive comparator | DiskANN bi-metric search · 6 large BEIR datasets (avg) | Gemini API calls at equal accuracy: ≈800 -> ≈200 calls | Improved |
| build index with cheap metric d instead of expensive metric D (single metric) | DiskANN bi-metric search · 6 BEIR datasets, NDCG@10 | convergence speed | Improved |
| use a cheap proxy model with a larger quality gap to the expensive model (ablation) | bi-metric search · HotpotQA (bge-micro, gte-small, bge-base) | NDCG@10 gain over re-ranking | Improved |
| start second-stage search from top-100 or top-Q/2 first-stage results instead of top-1 or the default entry point (ablation) | bi-metric second-stage search · HotpotQA | NDCG@10 | Improved |
| start second-stage search from only the top-1 first-stage point (ablation) | bi-metric second-stage search · HotpotQA | NDCG@10 | Hurt |
| swap DiskANN for NSG as graph index (ablation) | bi-metric search · BEIR retrieval | NDCG@10 | No clear effect |
| apply bi-metric framework to LSH-style partition methods | LSH · theory (adversarial dataset) | query time | Hurt |
Closest papers by meaning
- Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations (NeurIPS 2023 · similarity 0.88)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.88)
- Scalable Nearest Neighbor Search for Optimal Transport (ICML 2020 · similarity 0.87)
- Online Nearest Neighbor Search Using Hamming Weight Trees (TPAMI 2019 · similarity 0.87)
- Graph-based Nearest Neighbors with Dynamic Updates via Random Walks (ICLR 2026 · similarity 0.87)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.85)
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.
