algorithm - K-d树: nearest neighbor search algorithm with tractable pseudo code

Question

维基百科中最近邻(NN)搜索的伪代码对我来说不够容易处理。关于实现的帖子很少，但它们似乎是特定于语言的。所以我发现很难理解神经网络搜索是如何工作的。此图取自https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf 。我试图用一个特定的案例来理解它，比如查询点 Q = (52,52)。 假设两个暗度为 (x,y)，并且根级别按 x-dim 分割。

搜索神经网络:

首先，我从根到叶，就好像我试图插入 Q；这样做，叶子是(55,1)。将(全局)变量 current_best 从 INFINITY 更新为 (55-52)² + (1-52)² = 2610。

接下来，我转到 (70,70) 并将 current_best 从 2610 更新为 18²+18²=648。由于这提供了更好的距离，我们必须探测它的子树:这是正确的理解吗？

此外，我们看到节点 (60,80) 没有给出更好的结果(即没有更新 current_best)。

在进一步上升的过程中，我们发现 root (51,75) 给出了更好的结果(current_best 设置为 530)。因此，根据我的理解，我们必须检查它的其他子树。

(25,40) 不会产生任何更好的结果。我的理解是，我们还需要验证(25,40)的子树。然而，在这种情况下，由于该节点使用 y-dim，并且由于 Q.y > 40，因此我们只需要检查右子树(以 (35,90) 为根): 这是正确的理解吗？

简而言之，我看到的是，如果一个节点为 current_distance 提供了更好的结果，我们必须探测两个子节点；如果一个节点不能提供更好的结果，我们所能做的就是忽略其中一个子树，但必须根据条件(按特定维度分割超平面)探测另一个子树。 这是正确的理解吗？

最后，我非常感谢任何为 Kd 树的 NN 搜索提供易于处理的伪代码的人

Answer 1

想象目标点和它周围的一个圆盘，其半径等于迄今为止找到的最短距离(最初为无穷大)。

您位于一棵树的根部，该树将平面分成两个半平面。使半径等于当前半径和目标到根的距离中的最小值。然后递归到与圆盘相交的半平面，只要根有儿子。

确保记录哪个根达到最小值。

Visit(root):
    d= distance(target, root)
    if d < r:
        r= d
        closest= root

    if root.left and root.x - target.x < r:
        Visit(root.left)
    if root.right and target.x - root.x < r:
        Visit(root.right)

注意:半平面测试在 x 或 y 上进行，具体取决于您使用的轴选择策略。