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).

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

还有，谁能解释一下关于超空间和超平面的部分？我觉得我明白了，但因为我不确定我想要更多的解释。

谢谢!

Answer 1

每个节点沿一个轴将空间分成 2 个半空间。您查看所讨论的点相对于该分割平面的位置，以决定从树的哪一侧下降。例如，如果您的点是 (4,7,12) 并且您有一个在 9 处切割 y 轴的分割平面，您将比较 7 和 9 并决定沿着点的左侧(小于)向下首先是k-d树。在左侧找到最近的邻居后，您然后检查它是否比 2 更近(到分割平面的距离:9-7)。如果它比 split 平面更近，则根本不需要遍历另一半树。这就是它运作良好的原因，大多数时候您只需遍历一棵子树。

希望对您有所帮助。