algorithm - 如何使用 KDTrees 实现最近邻搜索？

Question

所以，我正在实施一个KD-Tree来进行最近邻搜索。我已经让构建树部分工作，但我认为我不完全理解搜索部分。

关于遍历树搜索邻居，维基百科文章说如下：

Starting with the root node, the algorithm moves down the tree recursively, in the same  
way that it would if the search point were being inserted (i.e. it goes right or left 
depending on whether the point is greater or less than the current node in the split 
dimension).

“大于或小于 spit 维度中的当前节点是什么意思？我们是根据与查询的距离比较点还是通过拆分维度比较点？

另外，有人可以解释一下关于超空间和超平面的部分吗？我觉得我理解它，但由于我不确定我是否需要更多解释。

谢谢！

Answer 1

每个节点沿一个轴将空间分成 2 个半空间。您查看所讨论的点相对于该分割平面的位置，以决定树的哪一侧向下。例如，如果您的点是 (4,7,12)，并且您有一个在 9 处切割 y 轴的分割平面，您可以将 7 与 9 进行比较，然后决定向下（小于）首先是kd树。找到左侧最近的邻居后，检查它是否小于 2（到分割平面的距离：9-7）。如果它比分割平面更近，则根本不需要遍历另一半树。这就是为什么它工作得这么好，大多数时候你只需要遍历一个子树。

希望有帮助。