arXiv cs.AI· Amol Khanna, Edward Raff·· 3 天前AI 评分26
KNN 实现细节可大幅改变性能：以 Cover Tree 为例
KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees
AI 导读
研究者以 Cover Tree 为例推出统一 Rust 实现 RustKNN，涵盖三种构建变体与三种查询模式，发现实现细节会显著改变算法性能排名。最优查询策略取决于 k 与数据集，选错查询模式运行时最多差 7.5 倍；cover tree 的 base 参数在 dual-tree 搜索中并非安全默认值，1.3 仅在七个数据集之一上最优。
正文 · 原文
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