Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination

Summary: Adaptive early termination for ANN via per-query stop-point prediction with gradient-boosted trees. Applied to FAISS-like ANN, it achieves up to 7.1x end-to-end latency reduction at the same accuracy on massive datasets; open-source at github.com/efficient/faiss-learned-termination. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5814
Venue: SIGMOD
Year: 2020
Pagerank: 0.00012463441
Overall Rank: 1,347 | 90.64%
DOI: 10.1145/3318464.3380600

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05
2,287	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.1004806e-05
2,687	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.3079951e-05
2,772	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.1491893e-05
2,997	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.7569625e-05
3,403	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	7.1338786e-05
4,524	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.1091797e-05
4,831	Vexless: A Serverless Vector Data Management System Using Cloud Functions	2024	SIGMOD	5.8883791e-05
5,236	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6077913e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
5,690	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	5.3699421e-05
6,970	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8740302e-05
7,235	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.7882389e-05
7,307	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	4.7623207e-05
8,430	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	4.508568e-05
8,484	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4956257e-05
8,495	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	4.4938255e-05
9,233	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	4.3648789e-05
9,296	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	4.3577746e-05
10,031	PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs	2026	SIGMOD	4.1905499e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1905499e-05
10,054	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD	4.1905499e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1905499e-05
10,141	Honeybee: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning	2026	SIGMOD	4.1905499e-05
10,154	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	4.1905499e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,187	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	4.1905499e-05
10,256	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.1905499e-05
10,275	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.1905499e-05
10,291	ConANN: Conformal Approximate Nearest Neighbor Search	2026	VLDB	4.1905499e-05
10,662	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	4.1905499e-05
10,744	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943
1,354	Northstar: An Interactive Data Science System	2018	VLDB	0.00012424105
1,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
3,019	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.699097e-05
4,963	Online Query Processing: A Tutorial	2001	SIGMOD	5.7979792e-05
5,218	Neighbor-Sensitive Hashing	2016	VLDB	5.6204105e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,524	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.1091797e-05
6,545	Flexible Aggregate Similarity Search	2011	SIGMOD	5.01361e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
10,691	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	4.1905499e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,052	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD	4.1905499e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1905499e-05
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981