快速 Kd-树用于 Kullback-Leibler 效散及其他可分解 Bregman 效散

本文的贡献涵盖理论和实现结果。首先，我们证明 Kd-树可以扩展到 ℝᵈ，距离由任意 Bregman 效散测量。或许令人惊讶的是，这表明三角不等式对于 Kd-树的正确剪枝并不是必需的。其次，我们提供了一种高效的算法和 C++ 实现，用于可分解 Bregman 效散的最近邻搜索。该实现支持 Kullback-Leibler 效散（相对熵），这是概率向量之间一种流行的距离，并在统计和机器学习中广泛使用。这是朝着扩大计算几何算法使用范围的一步。我们的基准显示，我们的实现高效地处理精确和近似的最近邻查询。与线性搜索相比，我们实现了在最高维度达到 100的实际场景中速度提高两个数量级。我们的解决方案比竞争方法更简单、更高效。