Cover Tree 实现细节如何显著改变 KNN 性能

01 摘要

该研究指出 KNN 搜索算法的实现细节在文献中常被忽略，但这些细节会实质性影响性能并改变算法优劣结论。作者以 Cover Tree 为例，用 RustKNN 统一实现三种构建变体和三种查询模式，发现最优查询策略取决于 k 和数据集，基参数默认值并非安全，微优化效果依赖维度。研究强调基准测试需报告实现细节，并公开了开源代码。

02 关键点

1. 最优查询策略依赖 k 和数据集：单树搜索在 k=1 时对四个最大数据集中的三个最快，双树搜索在 k≥5 时对三个最大数据集最快，选错查询模式可导致高达 7.5 倍的运行时间差距。
2. Cover Tree 基参数默认值不安全：理论值 2 和实践值 1.3 均非通用最优，1.3 仅在七个数据集中的一个上最优，在 covtype 上比最优值慢 1.6 倍。
3. 五种微优化中仅提前退出距离计算有一致效果，且随维度增加而增强：d=32 时无效果，d=54 时 1.31 倍，d=784 时 1.49 倍。