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

Amol Khanna; Edward Raff

cs.LGOct 12, 2026

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

Authors: Amol Khanna, Edward Raff

Organizations: CrowdStrike · University of Maryland, Baltimore County · Syracuse University

Abstract

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$ at $d{=}54$ , and $1.49\times$ at $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.

Figures & tables

Disabled optimization	pima	pendigits	corel	covtype	mnist
	( $d{=}8$ )	( $d{=}16$ )	( $d{=}32$ )	( $d{=}54$ )	( $d{=}784$ )
Early-exit distance	0.89 [0.73, 1.24]	0.82 [0.63, 0.99]	0.98 [0.97, 1.00]	1.31 [1.27, 1.36]	1.49 [1.39, 1.73]
Halfsort	1.28 [1.02, 1.42]	0.96 [0.75, 1.10]	1.10 [1.09, 1.11]	1.03 [1.03, 1.04]	1.02 [1.02, 1.03]
SmallVec	0.97 [0.89, 1.09]	0.65 [0.61, 0.95]	0.99 [0.98, 1.04]	1.01 [1.00, 1.02]	1.02 [1.01, 1.03]
$k{=}1$ fast path	1.06 [0.95, 1.28]	0.78 [0.69, 0.99]	1.04 [0.97, 1.06]	1.03 [1.03, 1.04]	1.01 [1.01, 1.02]
Triangle pre-filter	1.40 [1.28, 1.52]	0.75 [0.71, 0.79]	1.01 [0.98, 1.03]	0.98 [0.97, 0.99]	1.03 [0.96, 1.04]

Table 1: Ablation: slowdown (

\times

baseline) when each optimization is disabled (

k{=}1

, all-NN, base 1.3). Median [95% CI] over 20 independent allocations. Values

{>}1

mean the optimization helps; intervals spanning 1.0 indicate no reliable effect. Computed from the same pooled sample as the waterfall in Table 7 , so the “all off” row here and that table’s “baseline” row are identical by construction.

Dataset	$n$	$d$	Source	Dataset	$n$	$d$	Source
iris	150	4	UCI	optdigits	5,620	64	UCI
wine	178	13	UCI	pendigits	10,992	16	UCI
glass	214	9	UCI	letter	20,000	16	UCI
bupa	345	6	UCI	corel	37,749	32	UCI
ionosphere	351	34	UCI	mnist	60,000	784	LeCun
pima	768	8	UCI	covtype	581,012	54	UCI

Table 2: Benchmark datasets used in all experiments.

n

is the number of points and

d

is the dimensionality.

		RustKNN			C++	mlpack	mlpack
Dataset	$d$	Dual	Single	Batch	Ref	Single	Dual
iris	4	0.82 [0.80, 0.84]	0.37 [0.36, 0.38]	0.71 [0.68, 0.72]	0.33 [0.28, 0.35]	1.24 [1.03, 1.30]	1.32 [1.16, 1.35]
wine	13	0.82 [0.74, 0.85]	0.66 [0.57, 0.68]	0.74 [0.66, 0.76]	0.35 [0.27, 0.35]	1.18 [0.94, 1.20]	1.01 [0.81, 1.02]
glass	9	1.77 [1.41, 1.86]	0.96 [0.83, 1.05]	1.36 [1.15, 1.50]	0.54 [0.48, 0.60]	2.51 [2.23, 2.75]	2.22 [2.02, 2.46]
bupa	6	4.02 [3.48, 4.21]	2.07 [1.77, 2.21]	3.13 [2.58, 3.23]	1.27 [1.18, 1.41]	6.02 [5.64, 6.47]	6.17 [5.60, 6.77]
pima	8	7.29 [6.62, 8.66]	9.05 [8.09, 10.8]	6.68 [5.67, 7.38]	2.43 [2.26, 2.50]	13.5 [12.5, 13.9]	13.2 [11.9, 13.3]

Table 3: All-nearest-neighbor query time (ms,

k{=}1

, base 1.3). Median [95% CI] over 20 independent SLURM allocations. RustKNN results show three query modes: dual-tree, single-tree, and batch single-tree. Best result per row in bold .

k{=}10

results in Appendix Table 10 . Values

{\geq}10^{3}

are abbreviated K/M.

Dataset	Mode	$k{=}1$	$k{=}5$	$k{=}10$	$k{=}25$	$k{=}50$
optdigits	Dual	887 [886, 888]	1.09K [1.08, 1.1]	935 [837, 1,184]	979 [963, 1,106]	1.13K [1.12, 1.2]
	Single	160 [159, 165]	933 [885, 1,156]	772 [736, 902]	976 [962, 1,077]	1.21K [1.2, 1.26]
	Batch	979 [973, 1,129]	1.16K [1.06, 1.19]	987 [969, 1,143]	1.14K [1.13, 1.21]	1.34K [1.32, 1.42]
corel	Dual	4.96K [4.88, 5.17]	6.55K [6.3, 6.84]	7.58K [7.27, 7.86]	9.42K [8.97, 9.75]	11.5K [10.8, 11.9]
	Single	2.93K [2.69, 2.96]	8.12K [6.78, 8.32]	9.88K [8.22, 10.2]	13.1K [10.8, 13.5]	18.1K [13.5, 18.4]
	Batch	17.2K [17.1, 17.4]	21.4K [16.9, 21.5]	23.6K [19, 24]	28.1K [22, 28.9]	32.8K [25.5, 34.1]

Table 4: Query mode

\times

k

interaction (ms, all-NN, RustKNN Packed). Median [95% CI] over 20 independent allocations. Bold = best mode per

(\text{dataset},k)

. Values

{\geq}10^{3}

are abbreviated K/M.

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: All-nearest-neighbor query time comparison (

k{=}1

, base 1.3). Grouped bar chart across all 12 datasets with all six implementations.

Figure 2: All-nearest-neighbor query time comparison (

k{=}5

, base 1.3).

Figure 3: All-nearest-neighbor query time comparison (

k{=}10

, base 1.3).

		RustKNN Packed			C++	mlpack	mlpack
Dataset	$n_{q}$	Dual	Single	Batch	Ref	Single	Dual
pima	32	0.13 [0.11, 0.13]	0.10 [0.09, 0.10]	0.17 [0.16, 0.18]	0.09 [0.08, 0.09]	0.23 [0.22, 0.24]	0.69 [0.63, 0.70]
	128	0.57 [0.53, 0.57]	0.39 [0.36, 0.39]	0.52 [0.49, 0.53]	0.31 [0.28, 0.31]	0.93 [0.86, 0.94]	1.64 [1.51, 1.66]
	384	2.17 [2.00, 2.18]	1.15 [1.05, 1.16]	1.43 [1.30, 1.43]	0.79 [0.73, 0.80]	2.72 [2.51, 2.73]	3.59 [3.31, 3.64]
pendigits	32	0.93 [0.79, 1.05]	0.59 [0.52, 0.67]	1.05 [0.93, 1.16]	0.63 [0.52, 0.67]	1.66 [1.41, 1.78]	31.0 [27.7, 34.1]
	128	3.35 [2.97, 3.55]	2.32 [2.01, 2.49]	3.92 [3.45, 4.19]	2.22 [1.97, 2.34]	6.27 [5.51, 6.79]	76.1 [69.3, 81.7]

Appendix

Table 5: Held-out

k

-NN query time (ms,

k{=}1

) for varying numbers of query points

n_{q}

. Median [95% CI] over 20 independent allocations. Best per row in bold . pima has

n{=}768

, so its held-out split caps at

n_{q}{=}384

. Values

{\geq}10^{3}

are abbreviated K/M.

Figure 4: Held-out query scaling, traversal only (

k{=}1

). Query time vs. number of query points

n_{q}

Figure 5: Held-out query scaling, traversal only (

k{=}5

Figure 6: Held-out query scaling, traversal only (

k{=}10

Figure 7: Held-out query scaling, traversal only (

k{=}25

Figure 8: Held-out query scaling, traversal only (

k{=}50

Figure 9: Held-out query scaling, end-to-end (

k{=}1

). Query time vs. number of query points

n_{q}

Figure 10: Held-out query scaling, end-to-end (

k{=}5

Figure 11: Held-out query scaling, end-to-end (

k{=}10

Figure 12: Held-out query scaling, end-to-end (

k{=}25

Figure 13: Held-out query scaling, end-to-end (

k{=}50

	$k{=}1$			$k{=}10$
Dataset	Optimal $b$	Time (ms)	$b{=}1.3$ cost	Optimal $b$	Time (ms)	$b{=}1.3$ cost
glass	3.0	1.04	1.67 $\times$	3.0	2.08	1.55 $\times$
ionosphere	3.0	2.79	1.57 $\times$	3.0	5.00	1.39 $\times$
optdigits	2.0	653	1.02 $\times$	2.0	804	1.11 $\times$
pendigits	2.0	165	1.14 $\times$	2.0	273	1.17 $\times$
corel	2.0	4,773	1.11 $\times$	2.0	6,942	1.17 $\times$

Appendix

Table 6: Optimal base for RustKNN Packed dual-tree all-NN, with the cost of using the conventional

b{=}1.3

instead:

t(1.3)/t(b^{\star})

, so

1.00\times

means 1.3 is itself optimal. Medians over 20 independent allocations from the base-sweep campaign; the absolute times may differ from Table 3 due to cross-campaign variance. Bold = optimal

b

differs from 1.3.

Figure 14: All-nearest-neighbor query time (

k{=}1

) vs. base parameter. Each panel shows one dataset; implementations are color-coded. Medians over 20 independent allocations; shaded bands are bootstrap 95% CIs; stars mark the optimum of each implementation’s median curve. RustKNN curves show traversal time. For RustKNN Packed (dual-tree), base 1.3 is optimal on only 1 of 12 datasets (mnist) and within 20% of the best base on 5 of 12; elsewhere the optimum is 2.0, 3.0, or (on the two smallest sets) 5.0, and 1.5 on letter.

Figure 15: All-nearest-neighbor query time (

k{=}10

) vs. base parameter.

Figure 16: Held-out traversal query time (

k{=}1

) vs. base parameter.

Figure 17: Held-out traversal query time (

k{=}10

) vs. base parameter.

Figure 18: Held-out end-to-end query time (

k{=}1

) vs. base parameter.

Figure 19: Held-out end-to-end query time (

k{=}10

) vs. base parameter.

Configuration	pima	pendigits	corel	covtype	mnist
All off	1.00 [0.83, 1.21]	1.00 [0.93, 1.08]	1.00 [0.97, 1.03]	1.00 [0.98, 1.02]	1.00 [0.88, 1.13]
+Triangle	0.88 [0.77, 1.14]	1.00 [0.92, 1.03]	1.02 [0.99, 1.03]	1.03 [1.01, 1.04]	1.12 [0.98, 1.13]
+ $k{=}1$ fast	1.14 [0.97, 1.52]	0.99 [0.92, 1.03]	1.01 [0.96, 1.02]	1.02 [1.01, 1.03]	1.12 [0.98, 1.16]
+SmallVec	0.91 [0.79, 1.26]	1.00 [0.93, 1.04]	1.01 [0.99, 1.03]	1.06 [1.02, 1.09]	1.12 [0.98, 1.14]
+Halfsort	1.24 [0.87, 1.59]	0.96 [0.78, 1.23]	1.08 [1.05, 1.09]	1.02 [0.97, 1.05]	1.06 [0.86, 1.14]
+Early-exit	1.11 [0.99, 1.31]	0.78 [0.72, 0.83]	1.06 [1.03, 1.07]	1.33 [1.31, 1.34]	1.58 [1.39, 1.60]

Appendix

Table 7: Cumulative waterfall: speedup (

\times

all-off) as optimizations are added one at a time (

k{=}1

, all-NN, base 1.3). Median [95% CI] over 20 independent allocations. Optimizations are added in order of increasing sophistication. The “Baseline” row equals the “all off” row of Table 1 by construction (same pooled sample).

	corel ( $d{=}32$ )				covtype ( $d{=}54$ )				mnist ( $d{=}784$ )
Disabled	$k{=}1$	$5$	$10$	$50$	$k{=}1$	$5$	$10$	$50$	$k{=}1$	$5$	$10$	$50$
Early-exit	0.98	0.99	0.98	0.98	1.31	1.24	1.24	1.18	1.49	1.28	1.26	1.18
Halfsort	1.10	0.99	1.01	1.02	1.03	0.97	0.98	0.98	1.02	1.00	0.99	0.98
SmallVec	0.99	1.02	1.03	1.05	1.01	0.98	0.99	0.98	1.02	0.99	0.99	0.99
$k{=}1$ fast	1.04	0.91	0.91	0.94	1.03	0.96	0.98	0.98	1.01	0.99	0.99	0.99
Triangle	1.01	1.01	1.01	1.03	0.98	0.98	0.98	0.99	1.03	0.99	0.99	0.99

Appendix

Table 8: Per-

k

ablation slowdown factors (

\times

baseline, all-NN, base 1.3) for corel, covtype, and mnist. Values

{>}1

indicate the optimization helps. Median over 20 independent allocations at every

k

; the

k{=}1

column matches Table 1 by construction. Per-cell confidence intervals are omitted for width and are reported in the supplementary analysis output.

Dataset	Packed	NA Pk	NA	Simpl.	Parallel	C++
iris	5.27K	5.22K	5.22K	6.62K	7.63K	2.63K
wine	3.75K	4.25K	4.25K	9.47K	11.7K	2.64K
glass	12.9K	11.9K	11.9K	19.5K	22.2K	5.63K
bupa	36.7K	37.6K	37.6K	44.6K	60.9K	17.9K
pima	77.1K	88.8K	88.8K	208K	192K	41.9K
ionosphere	43.2K	50K	50K	45.8K	59.7K	18.1K

Appendix

Table 9: Distance computations for all-NN (

k{=}1

, base 1.3, dual-tree mode for Packed/NA Pk/NA, single-tree all-NN for Simplified/Parallel, the reference implementation’s batch query for C++) across all 12 datasets. Values in billions (B), millions (M) or thousands (K). The ablation in Section 4.2 measures the same dual-tree Packed mode, so its baseline counts are the Packed column here.

Panel of Figure 20 — Figure 20: Batch single-tree query. The query tree (blue, left) is traversed top-down by scale level. At each query split, children inherit filtered copies of the parent’s reference cover sets (red, right). A reference node pruned at $q$ is never seen by any descendant, amortizing the pruning decision across all queries in $q$ ’s subtree.

Panel of Figure 21 — Figure 21: Dual-tree traversal. At each internal pair $(q_{p},r_{p})$ , three phases execute: Phase 1 computes $d(q_{p},r_{i})$ for each reference child; Phase 2 computes $d(q_{j},r_{p})$ for each query child; Phase 3 evaluates all $q_{j}\times r_{i}$ pairs, using triangle inequality bounds from Phases 1–2 to prune without additional distance computations. Pruned pairs (gray) skip entire subtrees. The quadratic $|\text{children}_{q}|\times|\text{children}_{r}|$ expansion in Phase 3 is the main per-pair cost of the traversal.

		RustKNN			C++	mlpack	mlpack
Dataset	$d$	Dual	Single	Batch	Ref	Single	Dual
iris	4	1.33 [1.15, 1.37]	0.94 [0.77, 0.97]	1.46 [1.21, 1.48]	0.93 [0.80, 0.94]	2.67 [2.30, 2.68]	2.69 [2.38, 2.72]
wine	13	1.34 [1.11, 1.39]	1.44 [1.18, 1.51]	1.69 [1.40, 1.70]	1.10 [0.91, 1.16]	3.27 [2.67, 3.50]	2.33 [2.01, 2.53]
glass	9	2.83 [2.50, 3.28]	2.46 [2.14, 2.79]	2.86 [2.50, 3.28]	1.70 [1.51, 1.91]	5.51 [4.57, 5.94]	5.05 [4.17, 5.31]
bupa	6	6.46 [5.66, 6.88]	5.64 [4.80, 5.85]	5.44 [4.80, 5.82]	3.65 [3.42, 4.09]	11.4 [10.7, 13.6]	10.3 [9.51, 12.6]
pima	8	12.3 [10.5, 13.7]	20.0 [17.2, 22.5]	12.3 [10.9, 13.4]	7.50 [6.81, 7.55]	30.4 [28.7, 31.2]	23.6 [23.4, 25.1]

Appendix

Table 10: All-nearest-neighbor query time (ms,

k{=}10

, base 1.3). Companion to Table 3 (

k{=}1

). Median [95% CI] over 20 independent SLURM allocations. Best result per row in bold . Values

{\geq}10^{3}

are abbreviated K/M.

		Same codebase			Independent
Dataset	$d$	KD-tree	CT single	CT dual	kiddo
pendigits	16	71.9	171	199	7.77 [6.27, 9.80]
corel	32	254	3,248	5,702	59.1 [55.3, 70.8]
covtype	54	4,465	100,590	13,722	12,846 [12,777, 12,943]
mnist	784	4.09M	334,487	628,683	8.31M [8.29M, 8.34M]

Appendix

Table 11: Cross-structure and cross-codebase comparison (all-NN,

k{=}1

, ms). “KD-tree” and the two cover-tree columns share one codebase, kernel, and candidate structure, so their differences are attributable to the index itself. kiddo is an independent Rust KD-tree crate (median [95% CI] over 20 allocations) and isolates what changes when only the codebase differs. KD-tree and cover-tree columns come from the same dedicated single-allocation run, so that comparison is controlled same-run; the cover-tree values agree with Table 3 within 2% on covtype and within 7–19% on the other datasets, the differences reflecting cross-campaign variance (Section 5 ).

Disabled optimization	pima	pendigits	corel	covtype	mnist
	( $d{=}8$ )	( $d{=}16$ )	( $d{=}32$ )	( $d{=}54$ )	( $d{=}784$ )
Early-exit distance	0.90	0.98	0.99	0.97	1.11
Halfsort	0.62	1.04	1.00	1.00	1.01
SmallVec	1.02	1.01	0.99	0.98	1.00
$k{=}1$ fast path	1.09	1.00	1.00	1.01	1.00
Triangle pre-filter	0.70	1.00	1.00	0.99	1.02

Appendix

Table 12: KD-tree optimization ablation: slowdown (

\times

baseline) when each flag is disabled (

k{=}1

, all-NN). Directly comparable to the cover-tree ablation in Table 1 , since both share the distance kernel and candidate structure. Median of five runs in a single allocation.

Dataset	$d$	KD-tree distance evaluations
iris	4	1,126
wine	13	1,207
glass	9	1,534
bupa	6	2,914
pima	8	7,605
ionosphere	34	3,773

Appendix

Table 13: KD-tree all-NN metric evaluations (

k{=}1

), all 12 datasets. Cover-tree counts for all 12 datasets appear in Appendix E .

Dataset	$d$	Full (ms)	Partial (ms)	Speedup	$n^{2}$ distance calls
pima	8	5.2	4.6	1.14 $\times$	589,824
ionosphere	34	4.3	3.0	1.41 $\times$	123,201
pendigits	16	1,019	1,110	0.92 $\times$	120,824,064
optdigits	64	1,047	1,065	0.98 $\times$	31,584,400
letter	16	3,519	3,678	0.96 $\times$	400,000,000
corel	32	51,901	20,603	2.52 $\times$	1,424,987,001

Appendix

Table 14: Naive all-NN (

k{=}1

): full vs. partial distance computation. Both columns issue the same number of distance calls; the difference is per-call work avoided. Median of three runs in one allocation; on covtype, the six runs (three per variant) ran concurrently on one node so both variants saw the same load.

Sweep	Configuration	CT time (ms)	CT distance comps.	KD distance comps.
A: vary $d$ ( $D{=}100$ )	$d{=}2$	669	5,404,434	267,253
	$d{=}5$	1,203	8,782,805	267,248
	$d{=}10$	3,182	22,633,024	267,248
B: vary $D$ ( $d{=}5$ )	$D{=}20$	501	9,765,110	267,248
	$D{=}50$	918	10,985,580	267,248
	$D{=}100$	1,203	8,782,805	267,248

Appendix

Table 15: Synthetic manifolds (

n{=}20{,}000

, all-NN

k{=}1

). Cover-tree cost tracks the intrinsic dimension

d

and does not grow with the ambient dimension

D

. KD-tree distance counts are shown for contrast: they are near-identical (267K

\pm

5) across all configurations. Median of three runs in a single allocation.

Paper	Micro-opt.	Runtime & dist. counts	Batch vs. single	Set vs. held-out
[ 42 ]	0	0	0	0
[ 43 ]	0	0	0	0
[ 44 ]	0	0	0	0
[ 10 ]	0	0	0	0
[ 45 ]	0	0	0	0
[ 1 ]	0	0	0	1

Appendix

Table 16: Literature classification of 61 metric space search papers on four evaluation-practice criteria.

Exact Nearest Neighbor Search

See all 9 papers

Oct 10, 2026

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

Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on

SO(2)

SO(3)

and poses on

SE(2)

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

José Luis Blanco-Claraco

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

Exact Nearest Neighbor Search Tree Search

Ask PDF

Jul 10, 2026

Learning Partition Trees for Nearest Neighbor Search

We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset

P \subset \mathbb{R}^d

of size

n

and sample access to a query distribution over

\mathbb{R}^d

, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving

o(nd)

query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over

\mathbb{R}^d \times \mathbb{R}^d

and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an

α

fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree

\tilde{O}(1/\varepsilon^2)

that cuts at most an

O(\sqrt{α+\varepsilon})

fraction.

Sanjeev Khanna, Ashwin Padaki, Erik Waingarten

NYU · University of Pennsylvania

Exact Nearest Neighbor Search

Ask PDF

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

Abstract

Exact Nearest Neighbor Search

Explore similar work

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

Learning Partition Trees for Nearest Neighbor Search

Panorama: Fast-Track Nearest Neighbors