How to implement nearest neighbor search using KDTrees?

Question

So, I'm implementing a KD-Tree to do a nearest neighbor search. I've got the building the tree part working, but I don't think I understand the search part completely.

About traversing the tree to search for the neighbor, the Wikipedia article says the following:

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

What does "greater or less than the current node in the spit dimension mean? Do we compare the points based on distance from the query or do we compare the points by the split dimension?

Also, could someone explain the part about hyperspace and hyperplane? I feel like I understand it, but since I'm not sure I'd like some more explanation.

Thanks!

Phina

Answer 1

Each node splits the space into 2 half-spaces along one axis. You look at where the point in question is relative to that split plane to decide which side of the tree to go down. For example if your point is (4,7,12) and you have a splitting plane that cuts the y axis at 9, you'd compare the 7 to the 9 and decide to go down the left (less than) side of the k-d tree first. After finding the nearest neighbor on the left side, you then check if it is closer than 2 (the distance to the split plane: 9-7). If it is closer than the split-plane you do not need to traverse the other half-tree at all. This is why it works so well, most of the time you will only have to traverse one sub-tree.

Hope that helps.

Engram

I'd come to similar conclusions. Thanks! – Phina