algorithm - 计算两组 k 维向量的最小距离的快速方法

Question

我有两组k维向量，其中k在500左右，向量的个数通常更小。我想计算两组之间的（任意定义的）最小距离。一个天真的方法是这样的：

(loop for a in set1
      for b in set2
      minimizing (distance a b))

但是，这需要 O(n² * distance) 计算。有没有更快的方法来做到这一点？

Answer 1

当距离是任意的（你必须检查每个可能的距离！）时，我认为你不能比 O(n^2) 做得更好。对于给定的距离函数，我们可能能够利用该函数的属性，但不会有任何通用算法可以比 O(n^2) 更好地处理任何距离函数（即 o(n^2) ：注意小哦）。

如果您的数据是动态的，并且您必须在不同的时间不断获得最近的点对，那么对于任意距离函数，Eppstein 的以下论文可能会有所帮助（它们具有特殊的更新操作，以便快速找到最近的点对） ：

• http://www.ics.uci.edu/~eppstein/projects/pairs/Papers/Epp-SODA-98.pdf。[O(nlog^2(n)) 更新时间]

• http://academic.research.microsoft.com/Paper/1847461.aspx

您将能够将上述一组算法调整为两组算法（例如，通过将同一组的点之间的距离定义为无穷大）。

对于欧几里得类型 (L^p) 距离，有已知的 O(nlogn) 时间算法，它们适用于给定的一组点（即您不需要任何特殊的更新算法）：

• http://www.cse.iitd.ernet.in/~ssen/cs852/scribe/scribe2/lec.pdf
• http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

当然，L^p 是针对一组的，但是您也许可以将其调整为两组。

如果您提供距离函数，我们可能更容易为您提供帮助。

希望能帮助到你。祝你好运！

Answer 2

将两组坐标放入空间索引中，例如KD-tree。

然后计算这两个索引的交集。

Answer 3

如果你的向量的分量是标量，我猜对于你的中等 k=500 的情况，O(n²) 方法可能是你能得到的最快的。您可以通过最小化距离²来简化计算。此外，距离（A_i，B_i）= 距离（B_i，A_i），所以请确保您只比较它们一次（您只有 500！/（500-2）！对，而不是 500²）。

如果分量是 m 维向量 A 和 B，则可以将向量 A 的分量存储在R-tree或kd-tree中，然后通过遍历向量 B 的所有分量并找到其最近的伙伴来找到最近的对从 A --- 这将是 O(n)。不要忘记 big-O 用于 n->infinity，因此树可能带有一些非常昂贵的常数项（即这种方法可能只对大 k 或向量 A 始终相同时才有意义）。