nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds

José Luis Blanco-Claraco

cs.ROOct 10, 2026

nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds

Authors: José Luis Blanco-Claraco

Organizations: the Department of Engineering, CIESOL, CeiA3. University of Almería, 04120, Almería, Spain

Abstract

Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on $SO(2)$ or $SO(3)$ and poses on $SE(2)$ or $SE(3)$ , and a Euclidean KD-tree on their raw coordinates returns wrong neighbors. We present a header-only, dependency-free C++ KD-tree library for exact NN search on user-defined product manifolds declared at compile time: the space is composed from base manifolds ( $\mathbb{R}^n$ , $SO(2)$ , $SO(3)$ , $S^n$ ; products $SE(2)$ , $SE(3)$ , tori) with a single type alias, and the library synthesizes a metric whose pruning is provably admissible, wrap-aware for circular coordinates and double-cover-aware for unit quaternions. Experiments confirm exactness (recall $1.0$ vs an exhaustive scan under the same product metric), where the Euclidean-on-raw shortcut collapses to recall $\approx 0.5^{m}$ for $m$ rotation blocks, with up to three orders of magnitude speedup over brute force. We further contribute an incremental, self-balancing single-tree index for points under heavy churn (e.g. sliding-window LiDAR maps) or $SE(3)$ trajectories: bounded memory and faster updates than prior work, with an optional asynchronous tail-latency-bounding mode. The implementation is open source: https://github.com/jlblancoc/nanoflann

Figures & tables

Euclidean KD-tree / NN libraries
Method	Exact	Non-Eucl. spaces	Header-only	Dep.-free	Dynamic
FLANN [ 7 ]	approx/exact	none	–	–	–
ANN [ 8 ]	exact $+\epsilon$	none	–	–	–
libnabo [ 9 ] , PCL [ 10 ]	✓	none	–	–	–
pico_tree [ 11 ] , libkdtree++	✓	none	✓	✓	–
ikd-Tree [ 12 ]	✓	none	✓	$\sim$	✓

TABLE I : Feature comparison of NN libraries and methods (✓ yes,

\sim

partial, – no). Non-Eucl. spaces: “any” = arbitrary metric as a black box; “fixed” = a hard-coded factor set chosen at run time (MPNN:

\mathbb{R}

S^{1}

\mathbb{R}P^{3}

; nigh:

\mathbb{R}^{n}

SO(2)

SO(3)

SE(3)

, weighted Cartesian products); “general” = arbitrarily nested compile-time products of base manifolds, adding

S^{n}

(

n\geq 2

). The proposed library supports the manifold metric in both the static and the incremental single-tree index.

Panel of Figure 2 — Fig. 1 : Why a Euclidean KD-tree mis-prunes on non-Euclidean spaces. (a) On $SO(2)$ the query and its true nearest neighbor lie a short geodesic arc apart across the $\pm\pi$ seam but at opposite ends of the split coordinate, so the Euclidean point-to-cut bound prunes the far child, whereas the wrap-aware bound ( 2 ) measures the wrapped distance and explores it. (b) A quaternion block, on a cross-section of $S^{3}$ : the node box $R_{B}$ covers the arc its subtree occupies and is far from $v$ but close to the antipode $-v$ , the same rotation, so pruning on $d(v,R_{B})$ alone would discard it. The bound is the smaller of the two ambient point-to-box distances, $G_{B}=\min(d^{2}(v,R_{B}),d^{2}(-v,R_{B}))$ , reflecting the query , never the box; it is admissible because every $p\in R_{B}$ has $d^{2}(v,p)\geq d^{2}(v,R_{B})$ and $d^{2}(-v,p)\geq d^{2}(-v,R_{B})$ . Products follow blockwise, and for $S^{n}$ ( $n\geq 2$ ), its chordal metric is the ambient one.

Space	recall		$t_{\mathrm{KD}}$	$t_{\mathrm{BF}}$	speedup
	ours	naive	[ $\mu$ s]	[ $\mu$ s]	( $\times$ )
$SO(2)$	1.00	1.00	3.3	4573	$1399$
$S^{2}$	1.00	1.00	6.0	2936	$493$
$SO(3)$	1.00	0.50	139	3826	$27.6$
$SE(3)$	1.00	0.49	96	5252	$54.7$
$SO(3)^{2}$	1.00	0.26	747	6505	$8.7$

TABLE II : Manifold NN at

N=10^{6}

k=1

. Recall is against the exhaustive ground truth under the same metric ( 1 ).

t_{\mathrm{KD}}

t_{\mathrm{BF}}

: mean query times for the manifold KD-tree and brute force.

Panel of Figure 4 — Fig. 2 : Head-to-head vs. prior exact-manifold NN libraries (single thread, $k=1$ ). All methods are exact for their own metric. On pure $SO(3)$ , where all three share one ground truth, nigh’s intrinsic bound is fastest, but the proposed block-level bound now beats MPNN and stays within a small factor of nigh. The $SE(3)$ panel compares two exact solvers of different product metrics (see Table III ) on the same workload, so it reports cost, not ranking quality.

	$SO(3)$ (shared GT)			$SE(3)$ (own GT)
Library	build	$t_{q}$	recall	build	$t_{q}$	recall
	[ms]	[ $\mu$ s]		[ms]	[ $\mu$ s]
proposed	14	15	1.00	16	4.2	1.00
nigh	35	2.4	1.00	35	9.5	1.00
MPNN	195	45	1.00	–	–	–

TABLE III : Exact-manifold libraries at

N=10^{5}

k=1

(single thread). Build is index construction;

t_{q}

is mean query time. On

SO(3)

all three libraries induce the same ordering, so recall is against a single shared geodesic ground truth. On

SE(3)

they optimize different metrics (ours

\lVert\Delta t\rVert^{2}+w_{R}^{2}d^{2}_{\mathrm{chordal}}

; nigh

\lVert\Delta t\rVert+\theta

), so recall is against each method’s own exhaustive ground truth and the timings are not a like-for-like ranking comparison; the two metrics agree on the NN in only

{\sim}0.55

of queries.

seq	$N$	$t_{\mathrm{BF}}$	$t_{\mathrm{KD}}$	naive	naive	re-rank
		[ $\mu$ s]	[ $\mu$ s]	(canon.)	(sign-c.)
KITTI 00	4541	19.3	2.7	0.964	0.808	0.989
KITTI 02	4661	19.8	3.5	0.982	0.867	0.994
KITTI 05	2761	11.7	2.7	0.981	0.853	0.984
KITTI 06	1101	5.4	1.6	0.988	0.486	0.999
KITTI 08	4071	18.6	3.6	0.920	0.893	0.972

TABLE IV : Loop-closure retrieval on KITTI and MulRan keyframes (

w_{R}{=}15

k{=}8

, gap

100

frames). The proposed index is exact in all cells; columns give the recall of the naive 7-D Euclidean tree (canonicalized / sign-continuous quaternions) and of the 3-D-tree + re-rank workaround.

Panel of Figure 7 — Fig. 4 : Incremental index vs. alternatives on the sliding-window KITTI workload ( $4.8$ M-point map, $k{=}5$ ; single thread except the async variant’s background rebuild and ikd-Tree’s, which is always on). Top: CDF of per-frame update latency (steady state). Bottom: physically stored points; the synchronous tree stays within $1.3\times$ the live set, while the Bentley–Saxe forest never reclaims trimmed points.

Exact Nearest Neighbor Search

See all 9 papers

Oct 1, 2025

Panorama: Fast-Track Nearest Neighbors

Approximate Nearest-Neighbor Search (ANNS) pipelines for high-dimensional neural embeddings spend the bulk of their query time in candidate verification, making it the primary bottleneck in the search process. In this paper, we present PANORAMA, a state-of-the-art refinement technique that accelerates verification by exploiting the inherent spectral decay of these embeddings. Using PCA to compact signal energy, PANORAMA evaluates candidate distances incrementally, computing at each step a strict lower bound on the full-vector distance and dynamically pruning candidates the moment this bound exceeds the running k-th nearest neighbor distance. While PCA's concentration of variance facilitates pruning, it breaks the uniform-variance assumption required by Product Quantization (PQ); we resolve this with a variance-shaping step that redistributes energy across subvectors, rendering accretive refinement compatible with quantized indexes. Optimized for modern memory hierarchies via vectorized bulk-pruning and cache-conscious data layouts, PANORAMA has been upstreamed into the FAISS library across major index families (IVFPQ/Flat, HNSW, and Refine). PANORAMA achieves higher QPS at any target recall with a cost that provably scales inversely with dataset spectral decay, delivering end-to-end speedups of up to 28.9x and outperforming probabilistic methods across all recall bands.

Vansh Ramani, Alexis Schlomer, Akash Nayar +3

IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1

Product Quantization Approximate Nearest Neighbor Search

Ask PDF

Oct 12, 2026

KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees

Nearest neighbor search algorithms are widely used and have a long history, but we find that key implementation details are seldom reviewed in articles about them. These details can materially impact performance, and thus change the conclusions one makes about a given algorithm's superiority. In this article, we highlight these impacts by reviewing the Cover Tree as an example, producing RustKNN, a unified Rust implementation of three construction variants of the Cover Tree with three query modes. Our analysis reveals: (1) the optimal query strategy depends on

k

and on the dataset (single-tree search is fastest at

k{=}1

on three of our four largest datasets, while dual-tree search is fastest at

k{\ge}5

on the three largest), and choosing the wrong query mode can cost up to a

7.5\times

factor in runtime; (2) the cover tree base parameter, set to 2 in theory and 1.3 in practice, is not a safe default for dual-tree search: 1.3 is optimal on only one of seven datasets, and on covtype it is

1.6\times

slower than the optimum; (3) among five micro-optimizations, only early-exit distance computation has a consistent effect, and that effect grows with dimension (none at

d{=}32

1.31\times

d{=}54

, and

1.49\times

d{=}784

); and (4) all-nearest-neighbor and held-out benchmarks yield different implementation rankings. All main timing tables report medians over 20 independent allocations with bootstrap 95% confidence intervals. RustKNN is open source at https://github.com/CrowdStrike/RustKNN.

Amol Khanna, Edward Raff

CrowdStrike · University of Maryland, Baltimore County · Syracuse University

Exact Nearest Neighbor Search k-Nearest Neighbors Tree Search

Ask PDF

Jul 20, 2026

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

Approximate Nearest Neighbor Search (ANNS) plays a pivotal role in modern deep learning pipelines. Recently, many ANNS systems have been proposed to either provide broad functionality or reach high performance. However, it is yet difficult to achieve both with minimal programming efforts. We propose ANNLib to address the gap. ANNLib is a library that provides a programming framework for achieving high performance and flexible functionality in ANNS systems, based on popular graph-based ANNS algorithms. We carefully decouple and independently optimize both the algorithm and the data structure components of an ANNS system. In addition, we integrate state-of-the-art algorithms and data structures into ANNLib as modules, along with our new designs. Users can choose combinations of components to implement sophisticated settings with high performance, such as filter search, fully dynamic updates, and historical queries on snapshots. Our experiments show that our new solution provides a simple interface for various applications and achieves comparable or even better performance than previous work, specifically for each application.

Zheqi Shen, Jingbo Su, Zijin Wan +2

UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA

Exact Nearest Neighbor Search Graph-Based Retrieval Approximate Nearest Neighbor Search

Ask PDF

Abstract

Exact Nearest Neighbor Search

Explore similar work

Panorama: Fast-Track Nearest Neighbors

KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search