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

Question

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

我有两个问题：

1. 使用kd-tree是否会永久地将我与欧几里得距离联系起来？
2. 如果是这样，我应该尝试哪些其他类型的算法来处理任意指标？我没有太多时间来实现许多不同的数据结构，但我正在考虑的其他结构包括覆盖树和vp-trees。

Answer 1

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

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

Answer 2

我不认为您与欧几里得距离有关-正如 j_random_hacker 所说，您可能可以使用曼哈顿距离-但我很确定您与可以用笛卡尔坐标表示的几何形状有关。因此，例如，您不能使用 kd-tree 来索引度量空间。