如何使用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），並且你有一個分割平面將y軸切割爲9，那麼你會比較7和9，並決定沿着左邊（小於）首先是kd樹。找到左邊最近的鄰居後，檢查它是否接近2（到分割平面的距離：9-7）。如果它比分割平面更近，則不需要遍歷另一半樹。這就是爲什麼它工作得很好，大多數時候你只需要遍歷一個子樹。

希望有所幫助。