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

Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
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
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

Oct 1, 2025J/K move · Enter open · S save

Panorama: Fast-Track Nearest Neighbors

Vansh Ramani, Alexis Schlomer, Akash Nayar, Sayan Ranu+2

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

Product Quantization Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

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.

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