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

arXiv: https://arxiv.org/abs/2610.16940 · HTML: https://mlsanity.com/paper/2610.16940/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 88 references that are in the map.
- First posted on arXiv 12 Oct 2026.

## Builds on (most cited first, 10 of 10)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Research Reproducibility as a Survival Analysis](https://mlsanity.com/paper/2012.09932/) (2020)
- [What Do Machine Learning Researchers Mean by "Reproducible"?](https://mlsanity.com/paper/2412.03854/) (2024)
- [A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree](https://mlsanity.com/paper/2111.15478/) (2021)
- [A Siren Song of Open Source Reproducibility](https://mlsanity.com/paper/2204.04372/) (2022)
- [Tree-Independent Dual-Tree Algorithms](https://mlsanity.com/paper/1304.4327/) (2013)
- [Testing Scientific Software: A Systematic Literature Review](https://mlsanity.com/paper/1804.01954/) (2018)
- [Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006](https://mlsanity.com/paper/2208.09447/) (2022)
- [Toward Metric Indexes for Incremental Insertion and Querying](https://mlsanity.com/paper/1801.05055/) (2018)

## Abstract (arXiv)

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≥5 on the three largest), and choosing the wrong query mode can cost up to a 7.5× 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× 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× at d=54, and 1.49× 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.