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

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 four variants of the cover tree. Our analysis reveals: (1) the optimal query strategy depends critically on $k$, and can have up to $111\times$ factor impact on runtime; (2) the cover tree base parameter, set to 2 in theory and 1.3 in practice, tends to have an optimal value in $[1.1,2.0]$ which can be 20% faster than other settings for a given dataset; (3) micro-optimizations (early-exit distance, packing, triangle pre-filters) compose with early-exit distance being very powerful in high dimensions; and (4) all-nearest-neighbor and held-out benchmarks yield different implementation rankings. We release the implementation with reproducible benchmark infrastructure.