K-d 树：具有易处理伪代码的最近邻搜索算法

Question

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

正在搜索 NN：

首先，我从根向下到叶子，就好像我试图插入 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) 为根）： is this正确理解？

简而言之，我看到的是如果一个节点为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，具体取决于您使用的轴选择策略。

K-d 树：具有易处理伪代码的最近邻搜索算法

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

algorithm

data-structures

nearest-neighbor

kdtree