kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept.

However, I was said to study Kd-trees from Computational Geometry Algorithms and Applications (De Berg, Cheong, Van Kreveld and Overmars), section 5.2, page 99. The main difference I can see is that Overmars places the splitting data in the inner nodes and the actual points of the dataset in the leaves. For example, in 2D, an inner node will hold the splitting line.

Wikipedia on the other hand, seems to store points in inner nodes and leaves (while Overmars only on leaves).

In this case, how do we perform nearest neighbour search? Moreover, why there is this difference?

• What have you tried, and where did you get stuck? Have you studied regular search trees that store data only in the leaves, e.g. some flavors of B-trees?
– Raphael
Apr 10, 2014 at 14:42
• Well, in the case that we store points in all nodes (wiki case), I understand that we descend to a leaf, which is a good candidate for NN. Then we backtrack, as long as we find smaller distance from the current one, between the query and the splitting point. We may found the better candidate, in the parent node or in the other subtree. Right?? If so, in the case of Overmars,I will descend down to the leaf and then backtrack at the parent node where I check the distance with the splitting data and then descend if needed to the other subtree only? I am afraid of doing things that are not meant.. Apr 10, 2014 at 17:36
• This should help: stackoverflow.com/questions/13506226/… There are also papers you can find for approximate k-NN queries on kd trees. Apr 11, 2014 at 10:27
• I have read the link before and also some papers. However, the store points in inner nodes too. My question focuses in the case that points are stored in the leaves only. How is the backtracking been performed then? Apr 11, 2014 at 12:54

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

Procedure NN(node), given query q
if(node is leaf)
Search all points, in node, update current best
else {internal node}
if( cut_coord(q) <= node's cut-value )
NN(left-child)
if( cut-coor(q) + current best distance > node's cut-value )
NN(right-child)
end if
else {cut-coor(q) > node's cut value}
NN(right-child)
if(cut-coor(q) - current best distance <= node's cut-value)
NN(left-child)
end if
end if(left/right)
end if(node)


In order to perform ANN search, see the answer here.