arXiv：cs.AI· Amol Khanna, Edward Raff·· 20 小时前
KNN 实现细节能大幅改变性能：以 Cover Tree 为例
KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees
AI 导读
研究以 Cover Tree 为例推出 RustKNN——用 Rust 统一实现三种构建变体与三种查询模式，发现实现细节会实质影响性能并改变算法优劣结论。最优查询策略依赖 k 与数据集，选错查询模式运行时最多差 7.5×；理论值为 2、实践中取 1.3 的 base 参数并非安全默认，在 covtype 上比最优慢 1.6×。
正文
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.5\times$ 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\times$ 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\times$ at $d{=}54$, and $1.49\times$ 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 this https URL.
| Comments: | 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Track on Evaluations and Datasets |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Information Retrieval (cs.IR) |
| Cite as: | arXiv:2610.16940 [cs.LG] |
| (or arXiv:2610.16940v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.16940 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Amol Khanna [view email]
[v1]
Mon, 12 Oct 2026 15:17:03 UTC (771 KB)
来源：arXiv：cs.AI · arxiv.org