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?
Default k-d-trees should split the data set at a point. This point is then stored on the inner node, and checked as neighbor when you walk down this tree at search time.
Of course you can have various variants of k-d-trees where the split may be at a different place, and when there is no element exactly at the splitting position, you can't have one in the inner node anymore.
Also, as k-d-trees are not dynamic, when simulating deletions via tombstones, the inner node may only contain a tombstone (representing a deleted object).