algorithm - 我可以使用任意指标来搜索 KD 树吗？

Question

我刚刚完成了一个 kd-tree 的实现用于进行快速最近邻搜索。除了 Euclidean distance 之外，我有兴趣使用不同的距离指标。 .我对 kd-tree 的理解是，如果度量是非欧几里德的，快速 kd-tree 搜索不能保证提供精确的搜索，这意味着如果我想尝试，我可能需要实现一个新的数据结构和搜索算法为我的搜索制定新指标。

我有两个问题:

1. 是否使用 kd-tree将我永久地绑在 Euclidean distance 上？
2. 如果是这样，我应该尝试哪些其他类型的算法来对任意 metrics 起作用？我没有太多时间来实现许多不同的数据结构，但我正在考虑的其他结构包括 cover trees和 vp-trees .

Answer 1

您链接到的维基百科页面上描述的最近邻搜索过程当然可以推广到其他距离度量，前提是您将“超球体”替换为给定度量的等效几何对象，并测试每个超平面是否与此交叉对象。

示例:如果您改用曼哈顿距离(即矢量分量中所有差异的绝对值之和)，您的超球面将变成(多维)菱形。 (这在 2D 中最容易可视化——如果您当前最近的邻居与查询点 p 的距离为 x，那么不同超平面后面的任何更近的邻居必须与宽度和高度为 2 倍且以 p 为中心的菱形)。这可能会使超平面交叉测试更难编码或运行更慢，但一般原则仍然适用。