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 仅在七个数据集之一上最优。
正文 · AI 翻译
摘要：最近邻搜索算法应用广泛且历史悠久，但我们发现关于它们的文章很少审视关键的实现细节。这些细节会实质性影响性能，从而改变人们对某一算法优越性的结论。在本文中，我们以 Cover Tree 为例来凸显这些影响，并由此产出 RustKNN——一个统一的 Rust 实现，涵盖 Cover Tree 的三种构建变体与三种查询模式。我们的分析揭示：(1) 最优查询策略取决于 $k$ 和数据集（在我们四个最大数据集中的三个上，单树搜索在 $k{=}1$ 时最快，而双树搜索在三个最大数据集上于 $k{\ge}5$ 时最快），选错查询模式最多可导致运行时相差 $7.5\times$；(2) cover tree 的 base 参数在理论上设为 2、实践中设为 1.3，但对双树搜索而言并非安全的默认值：1.3 仅在七个数据集中的一个上最优，而在 covtype 上它比最优值慢 $1.6\times$；(3) 在五项微优化中，只有提前退出距离计算具有一致效果，且该效果随维度增长（在 $d{=}32$ 时无效果，$d{=}54$ 时为 $1.31\times$，$d{=}784$ 时为 $1.49\times$）；以及 (4) 全最近邻与留出基准会得出不同的实现排名。所有主要计时表报告的是 20 次独立分配的中位数，并附有 bootstrap 95% 置信区间。RustKNN 已在 此 https URL 开源。
| Comments: | 第 40 届神经信息处理系统大会（NeurIPS 2026）。评估与数据集方向 |
| Subjects: | 机器学习（cs.LG）；人工智能（cs.AI）；信息检索（cs.IR） |
| Cite as: | arXiv:2610.16940 [cs.LG] |
| （或 arXiv:2610.16940v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.16940 arXiv 颁发的 DOI，经由 DataCite（待注册） |
Submission history
来自：Amol Khanna [查看邮箱]
[v1]
2026 年 10 月 12 日星期一 15:17:03 UTC（771 KB）
来源：arXiv cs.AI · arxiv.org