Research map / Graph learning / Graph algorithms and clustering
Understanding and Improving Proximity Graph Based Maximum Inner Product Search
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 |
|---|---|---|---|
| Add angular-graph search and initialize the inner-product graph search with neighbors of angular neighbors | ip-NSW · ImageNet | query time at recall 0.9: 5.5 ms -> 0.5 ms | Helped |
| Initialize candidates with MIPS neighbors of top-10 angular neighbors rather than top-10 MIPS neighbors | Candidate initialization · ImageNet | recall from candidates: 67.21% -> 97.22% | Helped |
| Use an angular graph in addition to the inner-product graph | ip-NSW · Yahoo!Music, WordVector, ImageNet, Tiny5M | recall-time performance | Helped |
| Use two proximity graphs and angular-neighbor candidate initialization | ip-NSW · ImageNet | similarity-function evaluations at a given recall | Helped |
| Use two proximity graphs and angular-neighbor candidate initialization | ip-NSW · ImageNet top-5 and top-20 MIPS | recall-time performance | Helped |
| Use ip-NSW+ instead of ip-NSW under changes to norm distribution | MIPS search · ImageNet, ImageNet-A, ImageNet-B | robustness of recall-time performance across distributions: 2.05, 1.55 and 1.37 | Helped |
| Use ip-NSW+ rather than ip-NSW on norm-shifted data | MIPS search · Yahoo!Music and WordVector variants | performance variation across variants | Helped |
| Use angular-graph parameters that are too small, such as M=1 or l=1 (ablation) | ip-NSW+ · ImageNet | recall-time performance: M=1; l=1 | Hurt |
| Use angular-graph parameters that are too large, such as M=20 or l=100 (ablation) | ip-NSW+ · ImageNet | recall-time performance: M=20; l=100 | Hurt |
| Vary angular-graph M and l around the default setting (ablation) | ip-NSW+ · ImageNet | recall-time performance | No clear effect |
| Increase dataset cardinality while keeping the norm distribution shape fixed (ablation) | Exact MIPS norm bias · ImageNet samples | share of top-10 MIPS results from top 5% norm items | Helped |
Closest papers by meaning
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.87)
- Faster Maximum Inner Product Search in High Dimensions (ICML 2024 · similarity 0.86)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.85)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.85)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.84)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.83)
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.