Research map / Learning theory and algorithms / Prediction and decision losses
Approximate Nearest Neighbor Search with Window Filters
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.
Defines c-approximate window search (ANN with numeric label range filters) and proposes a tree-based beta-WST framework that builds ANN indices at internal nodes, plus several query methods, achieving up to 75x speedup over baselines at 0.95 recall.
Problem
Approximate nearest neighbor search where each vector has a numeric label and queries must return neighbors whose labels fall within an arbitrary query range (window filter).
Approach
A beta-ary window search tree stores an ANN index (e.g., Vamana) at every internal node over contiguous label-sorted subsets; a query decomposes the filter range into a logarithmic number of node indices, giving provable correctness and runtime bounds. Also introduces super postfiltering over blowup-bounded range covers.
Key results
- Speedup of best method over best baseline at 0.95 recall reaches up to 75x on Deep at medium filter fractions (2^-8 to 2^-7).
- Up to 16x on SIFT, 9x on GloVe, and 17x on RedCaps at 0.95 recall.
- On the Adversarial dataset, Vamana WST and Three Split achieve good recall-latency tradeoffs while postfiltering baselines fail to reach meaningful recall.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the best proposed window-search method instead of the best baseline | Deep · Deep, filter fraction 2^-7; recall ≥0.95 | speedup over best baseline: 77.55 | Helped |
| Use the best proposed window-search method instead of the best baseline | SIFT · SIFT, filter fraction 2^-6; recall ≥0.95 | speedup over best baseline: 16.51 | Helped |
| Use the best proposed window-search method instead of the best baseline | GloVe · GloVe, filter fraction 2^-5; recall ≥0.95 | speedup over best baseline: 9.60 | Helped |
| Use the best proposed window-search method instead of the best baseline | Redcaps · Redcaps, filter fraction 2^-6; recall ≥0.95 | speedup over best baseline: 17.22 | Helped |
| Use the best proposed method instead of the best baseline | Deep · Deep, filter fraction 2^-1; recall ≥0.95 | speedup over best baseline: 0.75 | Hurt |
| Increase branching factor β (ablation) | Vamana WST · SIFT, filter fraction 2^-1 | recall | Hurt |
| Increase branching factor β (ablation) | Vamana WST · SIFT, filter fraction 2^-1 | build time and memory footprint | Helped |
Surprising findings
- Three Split performs comparably to Vamana WST on the adversarial dataset despite using postfiltering as a subroutine.
- Milvus and VBASE are dominated by the naive prefiltering and postfiltering baselines in experiments.
Limitations
- Super postfiltering and 2-WST incur substantial memory and build-time overhead (e.g., 53.2 GB vs 6.8 GB for Deep).
- Theoretical analysis assumes single ANN return while experiments measure top-10 recall.
- Slow-preprocessing Vamana with O(N^3) theoretical build time; experiments use fast-preprocessing variant.
Experimental setup
Datasets: SIFT GloVe Deep RedCaps Adverse
Benchmarks: SIFT GloVe Deep RedCaps Adverse
Metrics: recall@10 queries per second build time index memory speedup at 0.95 recall
Baselines: Prefiltering Postfiltering Milvus VBASE Optimized Postfiltering Super Postfiltering
Builds on: Vamana DiskANN segment tree Fenwick tree FilteredDiskANN
Closest papers by meaning
- Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations (NeurIPS 2023 · similarity 0.87)
- A Multilabel Classification Framework for Approximate Nearest Neighbor Search (NeurIPS 2022 · similarity 0.87)
- NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval (ICLR 2025 · similarity 0.85)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.85)
- LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table (CVPR 2025 · similarity 0.85)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor 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.