Research map / Graph learning / Graph algorithms and clustering
Graph Reordering for Cache-Efficient Near Neighbor Search
Benjamin Coleman, Santiago Segarra, Alex Smola, Anshumali Shrivastava
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 |
|---|---|---|---|
| reorder graph with Gorder | HNSW index · SIFT100M | L1 miss rate (%): 19.53 -> 14.46 | Improved |
| reorder graph with RCM | HNSW index · SIFT100M | L2 miss rate (%): 13.9 -> 7.61 | Improved |
| reorder graph with Gorder | HNSW index · SIFT100M | L3 miss rate (%): 6.5 -> 4.0 | Improved |
| reorder graph with Gorder | HNSW index · SIFT100M | TLB miss rate (%): 3.85 -> 2.14 | Improved |
| reorder graph with Gorder (cachegrind) | HNSW index · SIFT100M | L3 miss rate (%): 13.56 -> 8.32 | Improved |
| reorder graph with RCM (cachegrind) | HNSW index · SIFT100M | L1 miss rate (%): 22.76 -> 20.61 | Improved |
| lightweight degree-based reordering (DegSort, HubSort, HubCluster, DBG) | HNSW index · SIFT100M | L3 miss rate (%): 13.56 -> 13.34 | No clear effect |
| reorder graph with RCM | HNSW index · SIFT100M | P99 latency: 17\% | Improved |
| reorder graph with Gorder | HNSW index · SIFT100M | P99 latency: 30\% | Improved |
| reorder graph with objective-based methods | HNSW index · large datasets, high recall | query time: up to 40% | Improved |
| reorder graph with objective-based methods | HNSW index · small datasets (N<1M) | query time: 10\% | Improved |
| degree-based reordering | HNSW index · SIFT10M | query time | Mixed |
Closest papers by meaning
- Graph-based Nearest Neighbors with Dynamic Updates via Random Walks (ICLR 2026 · similarity 0.87)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.86)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.85)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.85)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.84)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.84)
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.
