QBAT: Model-based Query Budget Autotuner for Clustering-based Approximate Nearest Neighbor Search

Summary: QBAT uses offline query features to autotune per-query search budgets for clustering-based ANNS, replacing static budgets. GBDT and AlphaEvolve-derived heuristics optimize latency or recall consistency, cutting ScaNN’s searched budget by up to 68.8%. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: h5ab8cf7a2c3c23ca
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,848 | 27.07%
DOI: 10.14778/3836663.3836675

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Jonghyun Bae (Google)
2. Tae Jun Ham (Google)
3. Alan Li (Google)
4. Supawit Chockchowwat (Google)
5. Yannis Papakonstantinou (Google)

BibTeX Citation

@article{bae_vldb26,
        title = {{QBAT: Model-based Query Budget Autotuner for Clustering-based Approximate Nearest Neighbor Search}},
        author = {Bae, Jonghyun and Ham, Tae Jun and Li, Alan and Chockchowwat, Supawit and Papakonstantinou, Yannis},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {11},
        pages = {3091--3104},
        doi = {10.14778/3836663.3836675},
        url = {https://doi.org/10.14778/3836663.3836675},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
437	QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning	2019	VLDB	0.00018315867
4,598	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5086378e-05
9,136	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.2224279e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
2	10,323	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD
3	74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
4	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
5	2,821	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD
6	10,547	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD
7	345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
8	839	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD
9	10,900	ANNiE: A Learned Query Cost Estimator for Graph-Based Approximate Nearest Neighbor Search	2026	VLDB
10	10,874	BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector	2026	VLDB