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: 14519
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,578 | 27.43%
DOI: 10.14778/3772181.3772184

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 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585
406	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00019054532
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011508159
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,735	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.9004924e-05
3,265	New Trends in High-D Vector Similarity Search: AI-driven, Progressive, and Distributed	2021	VLDB	7.5834255e-05
4,212	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.8283344e-05
7,145	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6908957e-05
7,193	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6770249e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,364	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
2	7,145	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD
3	10,346	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD
4	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
5	9,892	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
6	926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD
7	6,746	Flexible Aggregate Similarity Search	2011	SIGMOD
8	9,163	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD
9	398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
10	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD