ConANN: Conformal Approximate Nearest Neighbor Search

Summary: ConANN applies conformal risk control to IVF ANN to deliver the first distribution‑free formal guarantees on approximation error (FNR). It adaptively probes clusters per query, often reducing probes and adding negligible overhead while matching target FNR. (summarized by gpt-5-mini on Mar 13 2026)

Paper ID: h5626efc586d9a5ee
Venue: VLDB
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,905 | 26.91%
DOI: 10.14778/3772181.3772184
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

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

Authors

1. Sonia Horchidan (KTH Royal Institute of Technology)
2. Fabian Zeiher (KTH Royal Institute of Technology)
3. Henrik Boström (KTH Royal Institute of Technology)
4. Paris Carbone (KTH Royal Institute of Technology)

BibTeX Citation

@article{horchidan_vldb26,
        title = {{ConANN: Conformal Approximate Nearest Neighbor Search}},
        author = {Horchidan, Sonia and Zeiher, Fabian and Boström, Henrik and Carbone, Paris},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {1},
        pages = {29--42},
        doi = {10.14778/3772181.3772184},
        url = {https://doi.org/10.14778/3772181.3772184},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,946	ConRAD: Conformal Risk-Aware Neural Databases	2026	VLDB	4.9605343e-05
11,101	Interoperability in Healthcare: A Primer and New Frontiers	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
281	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022262975
325	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020930941
578	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016079505
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
802	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013822222
837	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013530806
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,165	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011708765
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010092977
3,065	New Trends in High-D Vector Similarity Search: AI-driven, Progressive, and Distributed	2021	VLDB	7.6759702e-05
4,321	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.6519404e-05
6,812	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6597129e-05
7,286	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5493084e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,165	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
2	10,117	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
3	10,970	ANNiE: A Learned Query Cost Estimator for Graph-Based Approximate Nearest Neighbor Search	2026	VLDB
4	837	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD
5	8,281	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD
6	6,885	Flexible Aggregate Similarity Search	2011	SIGMOD
7	10,938	CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data	2026	VLDB
8	335	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
9	10,840	Harmonizing Efficiency and Accuracy in Filtered Vector Search	2026	VLDB
10	10,359	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD