How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range 0-127 and t is time, therefore monotonic increasing.

I want to be able to quickly search for points around a query point and think that constructing a kd-tree from the data is a good way to achieve that.

Now I can hardly construct a kd-tree by inserting each new point as, due to the monotonic increasing t, it will inadvertently become unbalanced.

Is there a way to create a "running" kd-tree, that is inserting elements on the one t-side, while dropping elements on the other t-side without the tree becoming unbalanced?

How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key. The maximum depth is determined by the number of bits. If x, y and t each have 32 bits, the depth is limited to 3*32=96 bits. Usually the depth is much less, because depth is solely determined by the type of data, not by the insertion order. Insertion and deletion time does also not change over time, only with the size of the tree.

The bit-interleaving imposes a z-order on the tree which helps with window queries by roughly translating spatial proximity into neighbourness in the tree.

A Java example, with support for kD-window queries, can be found here (my own code). THis also contains code to do the bit-interleaving, also for floating-point values.

If you do bit-interleaving, it may be worthwhile to transform the coordinates to a similar value range. For example if x and y range from 0 to 10000, then it may be useful to multiply and/or add a constant to t, such that it also ranges from 0-10000 (you can also transform x,y instead). This is not essential. You may also want to use t as the first dimension, because it sounds like you perform a lot of window queries over t to remove old values. Having t as first dimension should improve such queries.

If you are looking for something more sophisticated, especially with more dimensions or large datasets, there is the PH-Tree. It is similar to a bitwise trie, but uses larger nodes like a quadtree, so the maximum depth is more limited. The linked website also links sourcecode and a description, including a performance comparison of kDtree, bitwise tries (critbit tree) and PH-Tree.

Disclaimer: The last part is basically self-advertising, but to the best of my knowledge, the PH-tree may be the best solution in your case, at least if you have large datasets.

• I really like your thinking! You have just confirmed my thought process. I will have to look into the PH-trees, but apart from that I will probably go with your proposal. – fho May 3 '16 at 9:49