Research map / Learning theory and algorithms / Combinatorial and search optimization
Graph-Based Algorithms for Diverse Similarity 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 graph-based (DiskANN-style) algorithms that directly return k diverse approximate nearest neighbors, with provable guarantees under bounded doubling dimension and a heuristic version that beats post-processing on real and synthetic data.
Problem
Approximate nearest neighbor search where the k returned points must be diverse (colorful or under a diversity metric), avoiding the costly retrieve-then-rerank two-stage pipeline.
Approach
Modify DiskANN's graph construction so each node keeps out-edges to a diverse set of representatives (by color or diversity metric), and modify greedy search to maintain a diverse solution set, giving query time depending on k and log Δ rather than on the retrieval depth r.
Key results
- On the real-world seller dataset, diverse build plus diverse search reaches 95% recall@100 at about 1.5ms versus over 8ms for the post-processing baseline (about 5x).
- On the arXiv semi-synthetic dataset at 90% recall, the post-processing baseline takes about 90ms while diverse build plus diverse search takes about 25ms.
- Theoretically, the search takes O(k log_alpha(Delta/epsilon)) steps with approximation (alpha+1)/(alpha-1)+epsilon for low doubling dimension data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use diverse search with a standard DiskANN index instead of post-processing candidates | DiskANN on the real-world Seller Dataset · Real-world Seller Dataset, k'=1, 95% recall@100 | latency: upwards of 8ms -> ≈ 4.5ms | Helped |
| add diversity-aware index construction to diverse search | DiskANN on the real-world Seller Dataset · Real-world Seller Dataset, k'=1, 95% recall@100 | latency: ≈ 4.5ms -> around ≈ 1.5ms | Helped |
| use diverse search on a standard DiskANN index instead of post-processing | DiskANN on semi-synthetic arXiv · Semi-synthetic arXiv, high recall (say 90%) | latency: around 90ms -> around 135ms | Hurt |
| add diversity-aware index construction to diverse search | DiskANN on semi-synthetic arXiv · Semi-synthetic arXiv, high recall (say 90%) | latency: around 135ms -> around 25ms | Helped |
| increase diversity parameter m from 1 to 2 (ablation) | Diverse DiskANN index construction · Skewed SIFT | build time: 50 -> 53 | Hurt |
| increase diversity parameter m from 2 to 10 (ablation) | Diverse DiskANN index construction · Skewed SIFT | build time: 53 -> 55 | Hurt |
Surprising findings
- Diverse search on a standard (non-diversity-aware) DiskANN graph is slower than post-processing at high recall on arXiv (about 135ms vs 90ms), showing the index must be built with diversity in mind.
Limitations
- Theoretical guarantees assume bounded doubling dimension and aspect ratio.
- Production seller dataset is proprietary and synthetic colors are used for public datasets.
- Space and degree bounds grow with k and (8 alpha)^d, which can be large.
Experimental setup
Datasets: Amazon Automotive dataset Arxiv OpenAI embeddings SIFT
Benchmarks: Real-world seller dataset (20M vectors) Amazon Automotive Arxiv (skewed semi-synthetic) SIFT (skewed and balanced semi-synthetic)
Metrics: recall@100 query latency
Baselines: DiskANN with post-processing diversity reranking DiskANN build with diverse search
Builds on: DiskANN Gonzales greedy k-center HNSW
Closest papers by meaning
- Fast Diverse Nearest Neighbor Search (NeurIPS 2026 · similarity 0.92)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.88)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.87)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.87)
- LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table (CVPR 2025 · similarity 0.87)
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.86)
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.