PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Amol Khanna, Edward Raff

arXiv:2610.16940v1cs.LGcs.AIcs.IR

TL;DR

Nearest-neighbor papers often underreport implementation and evaluation details, although those choices can affect performance comparisons. The paper develops RUSTKNN as a controlled cover-tree implementation and finds that performance depends on dataset, k, and evaluation settings, with the wrong query mode costing up to 7.5× in runtime.

  • Problem

    Key implementation and evaluation details are seldom reviewed in nearest-neighbor papers, including whether performance is measured on held-out queries or training data.

    Source: §1 · p. 1

  • Method

    The paper develops RUSTKNN, a unified Rust implementation for controlled evaluation of cover-tree variants, query settings, and micro-optimizations.

    Source: §1 · p. 2

  • Results

    No single method dominates across datasets and query settings, and choosing the wrong query mode costs up to 7.5× in runtime.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Nearest-neighbor evaluations should document and assess relevant implementation and evaluation factors, or justify why only a subset matters for their use case.

    Source: §1 · p. 2

    The conclusions are scoped to single-threaded exact nearest-neighbor search under Euclidean distance on datasets up to approximately 581K points.

    Source: §2 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

This section motivates a controlled cover-tree study because implementation and evaluation choices are often underreported, then establishes the structure’s background and variants. The paper finds that no single method dominates across datasets and query settings.

1 Introduction

  • The paper argues for documenting evaluation details because papers often omit hold-out versus training-query performance, both runtime and distance counts, micro-optimizations, or batch versus single-query settings.RUSTKNN provides a controlled implementation for re-evaluating cover-tree variants, query settings, and implementation choices.Source: §1 · pp. 1–2
  • The best cover-tree configuration depends on dataset and query settings; choosing the wrong query mode costs up to 7.5× in runtime.The study also reports that base 1.3 is not a safe dual-tree default, early-exit benefits grow with dimension, and all-NN and held-out benchmarks yield different rankings.Source: §1 · p. 2

2 Related Work

  • Cover trees provide exact search over general metric spaces with query complexity tied to intrinsic rather than ambient dimensionality, making them the study’s case despite alternatives sharing some of these properties.The related-work discussion contrasts them with coordinate-based trees and approximate methods, while noting that navigating nets share the intrinsic-dimension property.Source: §2 · p. 2
  • RUSTKNN puts cover-tree variants and query modes in one codebase, addressing the confounding of algorithmic and implementation effects in cross-codebase comparisons; it also fills a gap in Rust’s exact metric-space search tooling.Existing cover-tree implementations do not share the same variants, modes, and optimizations, and none is Rust-native.Source: §2 · p. 3

3.1 Metric Spaces and the Doubling Dimension

  • The doubling constant c is dataset-dependent, and cover-tree query complexity is O(c^6 log n), rather than parametrized by ambient dimension D.Data on a low-dimensional manifold in R^D can have small c even when D is large.Source: §3.1 · p. 3

3.2 Cover Tree Invariants

  • Cover-tree levels encode progressively finer resolutions, while covering and separating invariants constrain parent-child and sibling distances; base b sets their distance ratio.Each node caches maxdist to support pruning when a query-to-node distance minus that bound exceeds the current best distance.Source: §3.2 · pp. 3–4

3.3 Algorithmic Variants

  • The study implements simplified, nearest-ancestor, and parallel construction variants alongside single-tree, batch single-tree, and dual-tree queries.Nearest-ancestor construction can tighten maxdist values but produces deeper trees, so it is not always faster to query; parallel construction is implemented but not timed.Source: §3.3 · p. 4

4 Implementation and Optimization Ablation

RUSTKNN packs cover trees for cache locality and uses feature-flag ablations to isolate optimization effects. Early-exit distance computation is the only consistently beneficial tested optimization, with stronger effects at higher dimensions.

4.1 Implementation Overview

  • RUSTKNN converts pointer-based trees into a depth-first contiguous PackedCoverTree, with each roughly 40-byte node fitting in a 64-byte cache line.The implementation uses a generic Distance<T> trait and adapts dual-tree traversal to cover trees without self-children.Source: §4.1 · p. 5

4.2 Optimization Ablation

  • The five feature-flagged optimizations include early-exit distance, halfsort, SmallVec, a k=1 fast path, and triangle pre-filters.Early exit checks partial distance sums against the pruning bound; the triangle pre-filter uses a lower bound to skip subtrees before metric evaluation.Source: §4.2 · p. 5
  • The ablation table reports slowdown when each optimization is disabled, using k=1 all-NN at base 1.3 across five datasets spanning dimensions 8 to 784.Values are medians over 20 independent allocations with bootstrap 95% confidence intervals; the five smallest UCI datasets were excluded as noise-dominated.Source: §4.2 · p. 5, Table 1 · p. 6
  • The batch-only sorted-vector tracking optimization was not evaluated because the ablation infrastructure targets all-NN dual-tree mode.Its impact is expected to scale with the number of concurrent query points in batch mode.Source: §4.2 · p. 5
  • 1.31× on covtype (d=54) and 1.49× on mnist (d=784) are the early-exit distance speedups; none was measured on corel (d=32).The dual-tree distance count stayed unchanged when early exit was disabled, and none of the five flags changed counts by more than 0.1%; the other optimizations had no consistent effect.Source: §4.2 · pp. 5–6, Table 1 · p. 6

5 Experiments

The experiments show that cover-tree rankings depend on query mode, k, dataset, and base parameter, while held-out tests and KD-tree comparisons reveal further ranking changes. Results are evaluated across varied Euclidean datasets using repeated allocations and confidence intervals.

5.1 Experimental Setup

  • Twelve Euclidean datasets span n=150–581,012 and d=4–784; timings use 20 independent allocations and bootstrap 95% confidence intervals.Each allocation is a separately scheduled job, and the reported value is the median over the 20 allocation medians.Source: §5.1 · pp. 6–7, Table 2 · p. 7

5.2 Query Mode × k Interaction

  • At k=10, dual-tree beats C++ by 1.9× on corel, 2.2× on covtype, and 3.6× on mnist; C++ has the lowest median on 9/12 datasets at k=1.Within RUSTKNN, mnist single-tree is 1.8× faster than dual-tree at k=1 but 3.1–3.5× slower at every k≥5; covtype dual-tree is best at every k, while single-tree is 7.0–7.5× slower. Single-tree’s tight pruning helps at k=1; as k grows, dual-tree’s joint pruning can outweigh its per-pair overhead.Source: §5.2 · pp. 7–9, Table 3 · p. 8, Table 4 · p. 8

5.3 Base Parameter Analysis

  • Across the twelve datasets, b=1.3 is optimal in only one of 24 dataset–k cases; on covtype it is 1.57× slower than the optimum at k=1.The authors recommend sweeping b across 1.3, 2.0, and 3.0 for dual-tree search, and do not generalize this recommendation to other implementations.Source: §5.3 · p. 9

5.4 All-NN vs. Held-Out Divergence

  • On covtype at nq=512, mlpack-Dual is 250× slower than mlpack-Single, while on mnist RUSTKNN dual-tree is 1.8× faster than single-tree.The authors recommend reporting both all-NN and held-out results: all-NN stresses scalability, while held-out approximates serving latency.Source: §5.4 · pp. 9–10

5.5 Beyond Cover Trees: A KD-Tree Under the Same Harness

  • At k=1, KD-tree is 13× faster than single-tree cover tree on corel, but at d=784 it is 12× slower; the same KD-tree algorithm also varies by up to 9× across codebases.The reported KD-tree advantage at moderate dimensionality is attributed to effective axis-aligned box pruning; at d=784 that pruning collapses.Source: §5.5 · p. 10

6 Conclusion

The study finds that cover-tree performance depends on interacting implementation and query choices, and that the best choice varies by dataset and setting. Its conclusions are limited to exact, single-threaded Euclidean search on datasets up to about 581K points.

6 Conclusion

  • The best query mode depends on k and dataset: single-tree often leads at k=1, dual-tree at k≥5 on the largest datasets, and a wrong mode costs up to 7.5×.The authors also report that b=1.3 is optimal in only one of 24 dataset–k cases for dual-tree search, while early-exit distance computation is the only micro-optimization with a consistent effect.Source: §6 · p. 10
  • All-NN and held-out benchmarks yield different implementation rankings, so the authors recommend reporting both.The paper reports its main results using medians over 20 independent allocations with bootstrap intervals.Source: §6 · p. 10
  • The conclusions cover exact Euclidean nearest-neighbor search, single-threaded, on datasets up to n≈581K; approximate methods, non-Euclidean metrics, parallel scaling, and larger n are unstudied.The authors interpret only ratios measured under the same node load.Source: §6 · p. 10

NeurIPS Paper Checklist

The checklist states that the abstract and introduction’s claims match the paper’s experimental contributions. It also notes explicit limitations and that the paper presents no new theoretical results or proofs.

1. Claims

  • The checklist reports that the abstract and introduction’s four claims correspond directly to the paper’s experimental sections.The claims cover optimization ablation, query-mode-by-k interaction, base-parameter analysis, and all-NN versus held-out divergence.Source: §1 · p. 18

2. Limitations

  • The checklist identifies an explicit Conclusion limitations paragraph that scopes the results and describes unstudied settings and measurement caveats.These include approximate methods, non-Euclidean metrics, parallel scaling, larger datasets, noise-limited small-set timings, and cross-codebase instruction-set disparity.Source: §2 · p. 18

3. Theory assumptions and proofs

  • The paper presents no new theorems or proofs; its theoretical foundations come from prior work.Source: §3 · p. 19

4. Experimental result reproducibility

The checklist describes the experimental methodology and implementation details as sufficient to reimplement the algorithms, while noting that benchmark harnesses and cluster scripts are not released. It also documents the use of repeated-allocation bootstrap intervals for many timing tables.

4. Experimental result reproducibility

  • Hardware and software specifications, compiler flags, methodology, and algorithm details are documented as sufficient to reimplement the experiments.Source: §4 · p. 19

5. Open access to data and code

  • The RUSTKNN library is open source, but the benchmark harness and cluster job scripts are not released.The measurement protocol, hardware, compiler flags, baseline versions, and public datasets are documented.Source: §5 · p. 19

6. Experimental setting/details

  • Dataset dimensions and sizes, experimental methodology, and hardware/software details are provided across the paper and appendix.Source: §6 · p. 20

7. Experiment statistical significance

  • Main-text timing tables report medians over 20 independent allocations with bootstrap 95% confidence intervals; the intervals capture between-allocation variability.The checklist notes that some base-parameter and ablation tables report medians without intervals, and that several appendix tables use runs within one allocation.Source: §7 · p. 20

8. Experiments compute resources

The paper reports that its experiments ran on a SLURM cluster and answers yes that compute-resource information is provided.

8. Experiments compute resources

  • The reproducibility checklist answers yes that the paper provides information about the computer resources used for experiments.Source: §8 · p. 21
  • Experiments ran on a SLURM cluster with Intel Xeon Platinum 8490H processors, one physical core per benchmark job, and similar node load across campaigns.Hardware and software details are described in the Appendix.Source: §8 · p. 21
  • The checklist asks papers to report compute-worker type, resources used per run, total compute, and whether the project required additional unreported compute.Source: §8 · p. 21

9. Code of ethics

The paper reports no human-subject research or high-risk model or dataset release, and describes its societal-impact assessment as not applicable.

9. Code of ethics

  • The work uses standard, publicly available machine-learning benchmark datasets and reports no crowdsourcing or human-subject research.Source: §9 · pp. 21, 23
  • The authors answer N/A on societal-impact discussion, stating the work concerns a foundational data structure and has no direct negative impact beyond general-purpose algorithmic research.Source: §9 · p. 21
  • The paper reports that no models or datasets with misuse risk are released, so safeguards for high-risk releases are marked not applicable.Source: §9 · p. 22
  • The authors report that existing datasets and baseline implementations are cited, with versions and licenses specified for the listed software assets.Source: §9 · p. 22
  • RUSTKNN is the new asset, released under the MIT license with a README, API documentation, tests, and runnable examples.Source: §9 · p. 23

A Experimental Figures

The appendix figures compare all-nearest-neighbor query times across implementations and show held-out query-time scaling for traversal-only and end-to-end measurements.

A.1 All-Nearest-Neighbor Query Comparison

  • Figures 1–3 compare all-nearest-neighbor query times across implementations at k=1, 5, and 10, using base b=1.3.Figure 1 covers 12 datasets and six implementations; bars are medians over 20 allocations and whiskers are bootstrap 95% confidence intervals.Source: §A.1 · p. 25, Figure 1 · p. 25, Figure 2 · p. 25

A.2 Held-Out Query Scaling (Traversal)

  • Figures 4–8 show held-out traversal-only query time as the number of query points nq varies, with median lines and bootstrap 95% confidence bands.Table 5 reports held-out k=1 query time in milliseconds across nq values; pima is capped at nq=384.Source: §A.2 · p. 26, Table 5 · p. 26, Figure 4 · p. 27

A.3 Held-Out Query Scaling (End-to-End)

A.4 Base Parameter Sensitivity

The appendix examines base-parameter sensitivity, experimental conditions, and implementation details for RUSTKNN.

A.4 Base Parameter Sensitivity

  • For RUSTKNN Packed dual-tree all-nearest-neighbor search at k=1, base 1.3 is optimal on only 1 of 12 datasets and within 20% of the best base on 5 of 12.The optimum is 2.0, 3.0, 5.0 on the two smallest sets, or 1.5 on letter for the other reported cases.Source: Figure 14 · p. 33

B Experiment Details

  • Benchmark jobs used one physical core and their own memory, but shared socket-level L3 cache and bandwidth; load-related variation widened some confidence bounds.The authors also note bimodal per-allocation timings on pima and pendigits for reasons not isolated.Source: B Experiment Details · p. 37
  • Rust builds use AVX-512 while the C++ builds use the default SSE2 instruction set, a stated confounder favoring Rust on vectorizable distance computations.Source: B Experiment Details · p. 37

C Implementation Details

C.1 Architecture and Trait-Based Generics

  • The Distance<T> trait lets users provide a distance method, while built-in Euclidean and Manhattan implementations include an optional bounded-distance method for early exit.The Euclidean implementation checks partial squared sums every 16–64 dimensions and returns a sentinel when the partial sum exceeds the squared upper bound.Source: §C.1 · p. 38

C.2 Packed Trees and Cache Optimization

The packed-tree and traversal choices shape memory layout and pruning, while the ablations show that early-exit distance computation supplies most of the combined speedup on higher-dimensional datasets.

C.2 Packed Trees and Cache Optimization

  • PackedCoverTree stores nodes contiguously with child links in a shared index array, and sorting children by parent distance puts closer children first.A PackedNode<f64> occupies approximately 40 bytes, with hot query fields spanning no more than 32 bytes and fitting within a 64-byte cache line.Source: §C.2 · p. 38

C.3 Dual-Tree Traversal

  • Dual-tree traversal handles missing self-children with point–subtree helpers, then uses three expansion phases and triangle-inequality lower bounds to prune child pairs.Per-query bounds are cached; the default uses full recursive B1/B2 bounds with epoch-based invalidation, while a cheaper kth-distance bound was removed because it can prune true neighbors.Source: §C.3 · p. 38

C.4 Parallel Construction

  • Parallel construction builds trees on equal-sized data chunks and merges them by binary reduction in O(log p) rounds, recomputing maxdist after merging.The merge algorithm aligns levels, recursively merges covered children, and reinserts uncovered points; construction is implemented but not timed in the experiments.Source: §C.4 · p. 39

D Full Ablation Tables

  • 1.33× on covtype and 1.58× on mnist are the cumulative speedups after adding early-exit, while the four preceding traversal optimizations contribute at most about 12%.On corel, the combined effect is 1.06× and early-exit does not increase it; the composition is largely additive on the large datasets because the optimizations target different bottlenecks.Source: Table 7 · p. 40, D Full Ablation Tables · p. 40
  • At k=50, early-exit’s benefit on covtype and mnist falls to 1.18× on both, while the other tested optimizations remain within a few percent of 1.0×.On corel, early-exit has no effect across k (0.98–0.99×); the apparent k=1 fast-path result at k≥5 is attributed to build-to-build layout rather than the optimization.Source: D Full Ablation Tables · p. 40, Table 8 · p. 40

E Distance Computation Tables

The appendix reports distance counts and query-time results alongside traversal diagrams and KD-tree comparisons. It describes controlled in-harness comparisons separately from results involving an independent library.

E Distance Computation Tables

  • The all-NN distance-count table covers 12 datasets and reports counts for multiple cover-tree variants and query modes, including dual-tree Packed mode.Its counts are for k=1 and base 1.3; the accompanying text identifies the ablation’s baseline counts with the Packed column.Source: Table 9 · p. 41, E Distance Computation Tables · p. 41

F Batch Single-Tree and Dual-tree Algorithm Diagrams

  • Batch single-tree traversal passes filtered reference cover sets from each query split to its children, so pruning at a query node also removes that reference node from descendant queries.Dual-tree traversal expands query/reference child pairs in three phases and uses bounds from the first two phases to prune without further distance computations.Source: Figure 20 · p. 42, Figure 21 · p. 42

G All-NN k=10 Results

  • Table 10 reports all-nearest-neighbor query time in milliseconds at k=10 and base 1.3, with medians and 95% confidence intervals over 20 allocations.The caption specifies that the best result per row is bolded and large values are abbreviated.Source: Table 10 · p. 43

H KD-Tree Baseline: Ablation and Cross-Codebase Comparison

  • The in-harness KD-tree shares the cover trees’ distance kernel, candidate structure, and timing code, while kiddo provides an independent-codebase comparison under the same 20-allocation protocol.The in-harness comparison isolates the index; kiddo uses its own kernel and candidate structure and therefore cannot run the ablation flags.Source: H KD-Tree Baseline: Ablation and… · p. 44, Table 11 · p. 44
  • On mnist, the in-harness KD-tree issues 594M distance computations versus 312M for the simplified cover tree in single-tree mode, as axis-aligned box pruning stops discriminating at high dimension.The appendix also reports that early-exit is the only KD-tree ablation flag with an effect beyond noise, reaching 1.11× at d=784 and approximately 1× at d≤54.Source: H KD-Tree Baseline: Ablation and… · p. 44

I Naive Search with Partial Distance Computation

The appendix compares partial-distance computation across search settings, tests cover-tree distance counts on synthetic manifolds with known dimensions, and surveys evaluation practices in 61 papers. Together, these passages report dataset- and protocol-dependent results and identify evaluation criteria that are seldom tested.

I Naive Search with Partial Distance Computation

  • 2.52× on corel, 1.65× on mnist, and 1.59× on covtype are the partial-distance speedups in a naive scan, while pendigits, letter, and optdigits show 0.92–0.98×.Both scan variants issue the same number of distance calls; on corel, early exit helps the scan but not the cover tree, consistent with the tree already pruning many far candidates.Source: I Naive Search with Partial Distance… · p. 46, Table 14 · p. 46
  • Naive all-NN scans require 3.6×10^9 distance calls on mnist and 3.4×10^11 on covtype, while the trees take milliseconds to minutes; scans remain competitive on the smallest datasets.The paper cautions against basing implementation decisions on the tiny-dataset results alone.Source: I Naive Search with Partial Distance… · p. 46

J Synthetic Manifolds with Known Intrinsic Dimension

  • 5.4M→8.8M→22.6M cover-tree distance computations accompany a fivefold increase in intrinsic dimension at fixed ambient dimension; increasing ambient dimension fivefold at fixed intrinsic dimension does not increase counts monotonically.The synthetic data contain 20,000 points sampled on a known-dimensional latent manifold and embedded in a higher-dimensional space.Source: J Synthetic Manifolds with Known… · p. 47, Table 15 · p. 47
  • 501→1,203 ms of cover-tree runtime accompanies the ambient-dimension sweep even though its distance counts do not rise monotonically, because each distance computation is D-dimensional.The passage cautions that distance counts alone would miss this runtime change.Source: J Synthetic Manifolds with Known… · p. 47

K Literature Survey: Evaluation Practices in Metric Space Search

  • Only 7 of 61 surveyed papers discuss micro-optimizations, 9 report both runtime and distance counts, 6 compare batch with single queries, and 16 test held-out queries.These four evaluation criteria correspond to the paper’s optimization ablation, joint runtime/count reporting, query-mode comparison, and all-NN versus held-out evaluation.Source: K Literature Survey: Evaluation… · p. 49

Related papers

Loading 2610.16940v1…