Research map / Graph learning / Graph algorithms and clustering
CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CSPG, which randomly partitions a dataset into sparse proximity graphs linked by shared routing vectors, with a two-stage search, to cut distance computations in graph-based ANNS.
Problem
Graph-based approximate nearest neighbor search spends many distance computations on unnecessary exploration during greedy beam search over large proximity graphs.
Approach
Randomly partition the dataset into several smaller, sparser proximity graphs that share routing vectors, and search first within one partition with a small candidate set, then across partitions via routing vectors with a larger candidate set.
Key results
- CSPG helps Vamana and HCNNG reach at least 1.5x QPS speedup at recall 0.9 on all four datasets.
- Index construction time and index size of CSPG are roughly 1.5x those of the base graph methods with default lambda=0.5, m=2.
- Speedup ratio decreases as dataset size grows (SIFT 0.1M to 5M) but CSPG still outperforms base methods, consistent with the theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CSPG to Vamana | Vamana · SIFT1M, GIST1M, DEEP1M, SIFT10M at Recall@10 0.9 | QPS speedup: at least 1.5x | Helped |
| Add CSPG to HCNNG | HCNNG · SIFT1M, GIST1M, DEEP1M, SIFT10M at Recall@10 0.9 | QPS speedup: at least 1.5x | Helped |
| Use 2 or 4 partitions instead of the unpartitioned baseline (ablation) | CSPG-HNSW, CSPG-Vamana, and CSPG-HCNNG · SIFT1M | QPS-recall performance | Helped |
| Increase the number of partitions (ablation) | CSPG · SIFT1M | QPS-recall performance | Mixed |
| Increase the routing-vector sampling ratio (ablation) | CSPG · SIFT1M and other evaluated datasets | QPS-recall performance | Helped |
| Set the first-stage candidate size to 1 (ablation) | CSPG-HNSW, CSPG-Vamana, and CSPG-HCNNG · SIFT1M and other evaluated datasets | QPS-recall performance | Helped |
| Increase dataset size (ablation) | CSPG compared with the corresponding original graph algorithms · SIFT10M sampled datasets | QPS-recall performance | Mixed |
Surprising findings
- ef1=1 (smallest first-stage candidate set) gave the best query performance in most cases.
Limitations
- Theoretical analysis assumes each partition has the same vector distribution as the full dataset, which holds only approximately in practice.
- Optimal number of partitions m depends on dataset distribution and must be tuned.
- Larger index size and construction cost (~1.5x) due to vectors duplicated as routing vectors.
Experimental setup
Datasets: SIFT1M GIST1M DEEP1M SIFT10M
Benchmarks: SIFT1M GIST1M DEEP1M SIFT10M
Metrics: QPS recall@10 number of distance computations index construction time index size
Baselines: HNSW Vamana HCNNG NSG faiss-ivf faiss-ivfpqfs
Builds on: HNSW Vamana HCNNG Monotonic Search Network NSG
Closest papers by meaning
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.87)
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.87)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.86)
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.85)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.85)
- Graph-Based Algorithms for Diverse Similarity Search (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.