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

arXiv:2610.16940v1 Announce Type: new 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.5imes 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.6imes 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.31imes at d{=}54, and 1.49imes 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.

Source: arXiv cs.LG | 2026-10-14