Kd tree: data stored only in leaves vs stored in leaves and nodes

Question

I am trying to implement a Kd tree to perform the nearest neighbor and approximate nearest neighbor search in C++. So far I came across 2 versions of the most basic Kd tree.

1. The one, where data is stored in nodes and in leaves, such as here
2. The one, where data is stored only in leaves, such as here

They seem to be fundamentally the same, having the same asymptotic properties.

My question is: are there some reasons why choose one over another?

I figured two reasons so far:

1. The tree which stores data in nodes too is shallower by 1 level.
2. The tree which stores data only in leaves has easier to implement delete data function

Are there some other reasons I should consider before deciding which one to make?

Krauss

@Boris Strandjev, Thank you! – Krauss

Why the second reason? I suppose that even with the second approach you store some distance data in intermediate nodes? – Innerve

@BorisStrandjev In the 1. st approach, if you delete a node, you need to find a replacement node. This can be implemented by searching the subtree rooted at that node. In the 2. nd approach you can just delete the leaf – Krauss

However you still need to update the data in the intermediate nodes? – Innerve

Yes, that is the better and more dilligent approach. But the 2nd tree leaves you the choice to do use the sloppy approach, without modifying the intermediate nodes. – Krauss

Answer 1

You can just mark nodes as deleted, and postpone any structural changes to the next tree rebuild. k-d-trees degrade over time, so you'll need to do frequent tree rebuilds. k-d-trees are great for low-dimensional data sets that do not change, or where you can easily afford to rebuild an (approximately) optimal tree.

As for implementing the tree, I recommend using a minimalistic structure. I usually do not use nodes. I use an array of data object references. The axis is defined by the current search depth, no need to store it anywhere. Left and right neighbors are given by the binary search tree of the array. (Otherwise, just add an array of byte, half the size of your dataset, for storing the axes you used). Loading the tree is done by a specialized QuickSort. In theory it's O(n^2) worst-case, but with a good heuristic such as median-of-5 you can get O(n log n) quite reliably and with minimal constant overhead.

While it doesn't hold as much for C/C++, in many other languages you will pay quite a price for managing a lot of objects. A type*[] is the cheapest data structure you'll find, and in particular it does not require a lot of management effort. To mark an element as deleted, you can null it, and search both sides when you encounter a null. For insertions, I'd first collect them in a buffer. And when the modification counter reaches a threshold, rebuild.

And that's the whole point of it: if your tree is really cheap to rebuild (as cheap as resorting an almost pre-sorted array!) then it does not harm to frequently rebuild the tree. Linear scanning over a short "insertion list" is very CPU cache friendly. Skipping nulls is very cheap, too.

If you want a more dynamic structure, I recommend looking at R*-trees. They are actually desinged to balance on inserts and deletions, and organize the data in a disk-oriented block structure. But even for R-trees, there have been reports that keeping an insertion buffer etc. to postpone structural changes improves performance. And bulk loading in many situations helps a lot, too!

Jhvh

Thank you very much for your detailed explanation. However there are a few points not clear to me. 1. what do you mean you do not use nodes? 2. Could you be more specific with regard to my question? The comparison of the two trees – Krauss

You can actually implement a kd-tree without having a node data type. Total memory cost: n pointers. And the simpler your code, the faster usually. What I'm also trying to convey is: you can implement either good or slow. There is no rule which one is better, but it depends on how well you can implement them for your specific needs. – Jhvh