Cover Tree Implementation Details Can Dramatically Change KNN Performance

01 ABSTRACT

This study points out that implementation details of KNN search algorithms are often overlooked in the literature, yet they materially impact performance and can change conclusions about algorithm superiority. Using Cover Tree as an example, the authors implement RustKNN with three construction variants and three query modes, finding that the optimal query strategy depends on k and dataset, the base parameter default is not safe, and micro-optimization effects depend on dimensionality. The study emphasizes that benchmarking should report implementation details and releases open-source code.

02 KEY FINDINGS

1. Optimal query strategy depends on k and dataset: single-tree search is fastest at k=1 on three of the four largest datasets, while dual-tree search is fastest at k≥5 on the three largest; choosing the wrong query mode can cost up to a 7.5× factor in runtime.
2. The Cover Tree base parameter default is not safe: neither the theoretical value 2 nor the practical value 1.3 is universally optimal; 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, which grows with dimension: none at d=32, 1.31× at d=54, and 1.49× at d=784.