Research map / Learning theory and algorithms / Prediction and decision losses
Improved nearest neighbor search using auxiliary information and priority functions
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 |
|---|---|---|---|
| store auxiliary information (c=500 candidate points, m=20 projections) at internal nodes of a single RPT for defeatist search | RPT (defeatist search) · six datasets, 1-NN | 1-NN accuracy: e.g. MNIST 12% -> 44%, SIFT 23% -> 47% | Helped |
| priority function fpr2 (distance-ratio weighted) instead of fpr1 for guided prioritized search (ablation) | guided leaf-visiting search on RPT · six datasets, 1-NN at 20 iterations | 1-NN accuracy: MNIST 61% vs 56%; SIFT 65% vs 61% | Helped |
| priority-based guided search (fpr1 or fpr2) instead of guided DFS | single RPT · six datasets, 1-NN at 20 iterations | 1-NN accuracy: MNIST fpr2 61% vs DFS 34%; SIFT 65% vs 40% | Helped |
| priority-based guided search (fpr2) instead of virtual spill tree at matched budget | single RPT · MNIST and SIFT, 1-NN | 1-NN accuracy: MNIST 61% vs 42%; SIFT 65% vs 58%; at low budgets virtual spill tree is comparable (e.g. MNIST 15% vs 19% at 2 iter) | Mixed |
| increasing number of leaf nodes visited (iterations) in prioritized search | fpr2 guided search · six datasets, 1-NN | 1-NN accuracy: gains diminish with more iterations | Helped |
| combine auxiliary-information defeatist search with priority-guided leaf search (single tree) vs fewer leaves | single RPT · six datasets, 10-NN budget of 20 leaves | 10-NN accuracy: MNIST 72% single tree at 20 iter; combined approach yields lower rank-error than normal RPT | Helped |
| use 3 trees with ~7 iterations each (Multi-Combined) instead of 1 tree with 20 iterations (ablation) | combined approach · six datasets, 10-NN budget of 20 leaves | 10-NN accuracy: MNIST 72% -> 89%; SIFT 55% -> 74%; SIAM07 19% -> 24% | Helped |
| increase number of trees in Multi-Combined beyond three (ablation) | Multi-Combined · six datasets, 10-NN | 10-NN accuracy: accuracy increases very slowly beyond three trees (e.g. MNIST 89% -> 91% -> 93% for 3/4/5 trees) | No clear effect |
| Multi-Combined (3 trees) instead of normal RPT forest at matched iterations/trees | forest of RPTs · six datasets, 10-NN accuracy vs retrieved ratio | 10-NN accuracy: higher accuracy with less space than normal RPT (Figure 4 only, no numeric values) | Helped |
Closest papers by meaning
- An algorithm for L1 nearest neighbor search via monotonic embedding (NeurIPS 2016 · similarity 0.89)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.87)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.85)
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.85)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.85)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · 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.