Exact Nearest Neighbor Search

Follow this topic Ask about this topic

Latest papers

9 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

CertEx: Exact Visual Retrieval at Scale by Certified Exclusion
Oct 15, 2026Dongfang ZhaoExact Nearest Neighbor Search k-Nearest Neighbors
Tacoma School of Engineering & Technology and eScience Institute, University of Washington
KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees
Oct 12, 2026Amol Khanna, Edward RaffExact Nearest Neighbor Search k-Nearest Neighbors
CrowdStrike · University of Maryland, Baltimore County · Syracuse University
nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds
Oct 10, 2026José Luis Blanco-ClaracoExact Nearest Neighbor Search Tree Search
the Department of Engineering, CIESOL, CeiA3. University of Almería, 04120, Almería, Spain
ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search
Jul 20, 2026Zheqi Shen, Jingbo Su, Zijin Wan +2Exact Nearest Neighbor Search Graph-Based Retrieval
UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA
Learning Partition Trees for Nearest Neighbor Search
Jul 10, 2026Sanjeev Khanna, Ashwin Padaki, Erik WaingartenExact Nearest Neighbor Search
NYU · University of Pennsylvania
HNSW with Accuracy Guarantees Using Graph Spanners
Jul 2, 2026Minghao Li, Raghav Mittal, Sanjivni Rana +3Exact Nearest Neighbor Search Graph-Based Retrieval
University of Toronto Toronto, Canada · The University of Texas At Arlington Arlington, Texas, USA · IIT Bombay Mumbai, India
Exact and Deterministic Patch Descriptor Retrieval via Hierarchical Normalization
Jun 25, 2026Koichi SatoBranch and Bound Exact Nearest Neighbor Search
Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
Jun 15, 2026Madhulatha Mandarapu, Sandeep KunkunuruExact Nearest Neighbor Search Regret Minimization
VaidhyaMegha Private Limited, India
Fast Exact Nearest-Neighbor Learning for High-Frequency Financial Time Series
Jun 8, 2026Henry Han, Diane LiQuantitative Finance Efficient Inference
Data Science and Artificial Intelligence Innovation Laboratory, School of Engineering and Computer Science, Baylor University, Waco, TX 76798, USA · Department of Business, Management and Accounting, University of Maryland Eastern Shore, USA

Oct 15, 2026J/K move · Enter open · S save

CertEx: Exact Visual Retrieval at Scale by Certified Exclusion

Dongfang Zhao

Tacoma School of Engineering & Technology and eScience Institute, University of Washington

Exact Nearest Neighbor Search k-Nearest Neighbors Image Retrieval

Open paper AskPDF arXiv

Exact

k

-nearest-neighbor (kNN) search over image descriptors and embeddings underlies visual retrieval, near-duplicate detection, the evaluation of learned representations, and increasingly the memory of LLM agents. However, exhaustive search computes every distance at full precision, whereas approximate indexes return recall below one. We observe that exact search only needs a proof that each excluded vector cannot be a neighbor. Because such a proof only has to be conservative, it can be checked in low precision, much as the retina examines the whole scene at low resolution. We call this principle certified exclusion and realize it in an exact kNN method for GPUs, which we call CertEx. Specifically, CertEx stores a lower-bounding projection of each vector in half precision and folds a rounding certificate into the same tensor-core dot product, so that only the few vectors that the test keeps need exact distances. We prove that CertEx returns the exact kNN of every query. On sixteen datasets with up to 100M vectors, CertEx is exact for every query at 7.1

\times

to 18.0

\times

the throughput of the fastest cuVS search on one H100 (8.8

\times

to 11.8

\times

on an A100) and outperforms quantized and graph indexes whenever every query must be exact.