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

Question

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

搜索神经网络:

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

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

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

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

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

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

最后，我真的很感谢任何人为 NN 搜索 Kd-tree 提供易于处理的伪代码

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 上进行，具体取决于您使用的轴选择策略。