Research map / Learning theory and algorithms / Prediction and decision losses

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

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Re-implements cover trees in a unified Rust library (RUSTKNN) and shows that implementation details (query mode, base parameter, micro-optimizations, all-NN vs held-out evaluation) can change performance rankings substantially.

Problem

Exact k-nearest-neighbor search results and rankings depend on implementation details (query mode, base parameter, micro-optimizations, evaluation protocol) that are rarely reported, so cross-codebase comparisons confound algorithmic and implementation effects.

Approach

Build a single controlled Rust codebase implementing three cover tree construction variants and three query modes with feature-flag ablations of micro-optimizations, then measure how each factor changes runtime across k, datasets, and evaluation protocols using repeated independent allocations with bootstrap CIs.

Key results

• Optimal query mode depends on k and dataset: single-tree is fastest at k=1 on three of four largest datasets, dual-tree at k>=5 on the three largest; wrong mode costs up to 7.5x on covtype.
• Base 1.3 is optimal on only 1 of 12 datasets for dual-tree all-NN; on covtype it is 1.57x slower than the optimum at k=1.
• Early-exit distance is the only micro-optimization with consistent effect, giving 1.31x at d=54 and 1.49x at d=784 and none at d=32.

Surprising findings

• Base parameter 1.3, recommended in the original cover tree work, is rarely optimal for dual-tree search; coarser bases win in most cases.
• All-NN and held-out benchmarks produce different implementation rankings; mlpack dual vs single differ by up to 250x held out but are within 2x in all-NN.

Limitations

• Scoped to exact Euclidean search, single-threaded, datasets up to n~581K; approximate methods and parallel scaling not studied.
• Timings on the smallest datasets are noise-dominated and bimodal; large-dataset timings measured on loaded nodes.
• Cross-codebase comparisons carry an instruction-set disparity (AVX-512 for Rust vs SSE2 for C++).

Experimental setup

Datasets: iris wine glass bupa ionosphere pima optdigits pendigits letter corel covtype mnist

Benchmarks: all-nearest-neighbor query on 12 UCI/MNIST datasets held-out k-NN query scaling

Metrics: median query time (ms) with bootstrap 95% CI distance computation counts slowdown factor from ablation

Baselines: C++ cover tree reference (Beygelzimer et al.) mlpack cover tree single-tree mlpack cover tree dual-tree kiddo

Builds on: cover tree (Beygelzimer et al.) Izbicki and Shelton simplified and nearest ancestor cover trees dual-tree traversal (Curtin et al.)

Closest papers by meaning

• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations (NeurIPS 2023 · similarity 0.86)
• Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.84)
• Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.83)
• Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.83)
• Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.83)
• Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.82)