kdtree or balltree supporting insertion/deletion

Question

I'm looking for a data structure to perform nearest-neighbor searches in 3D Euclidean space. I have used kd- and balltrees for this purpose before, but my problem is more sophisticated this time. I'd like to be able to insert and delete points from my dataset dynamically. I don't see any reason why either of these two data structures wouldn't support this. Based on my understanding of both algorithms, I would think they offer the same complexities for each operation as a 1D binary search tree, including logarithmic-time insertion and deletion. Yet I can't find an implementation of either type of tree that supports these operations.

Why do none of the kdtree and balltree implementations I can find online (in particular from sklearn and alglib) support insertion/deletion? Is there a different freely available implementation which does?

Answer 1

My experience comes mainly from kd-trees.
I think this answers part of your question and the attached image really visualizes the problem.
When you construct the kd-tree initially the tree is constructed in a way that is balanced.
If you add vertices to the tree, especially if you are adding points in a trajectory (e.g. the points that an airplane traversed) then you end up with an unbalanced tree where query time are not as good as balanced trees.

Answer 2

I am not sure about BallTrees, but kd-trees definitely support deletion (see my Java implementation here). I think the reason why it is often not implemented is that it is a lot more complex and may be a lot slower than a typical insertion. For example, you first need to find a proper replacement point.

As @Andrea Nardi pointed out, in kd-trees insertion and deletion usually cause imbalances in the tree making it slower (I would add that the initial tree is also usually imbalanced).

If you are looking for spatial index that support nearest neighbor search and fast insertion/deletion, also have a look at my own PH-Tree. It works a bit like a quadtree but can guarantee a maximum depth and is much more memory efficient. It also guarantees that every insertion/deletion will only affect one node (and possible add/remove an empty second node). Note that the standard implementation is a map, so every coordinate can have only one entity, you would need to store lists at each coordinate.

In my experience quadtrees and the PH-Tree are the fastest for insertion/deletion. The PH-Tree scales well with large datasets (millions of points). For 3D nearest neighbor search, the best often seem to be R-Trees (e.g. R-star-tree), and again quadtrees and the PH-Tree (quadtree being the fastest but not scaling well with entry count). I found kd-trees usually lacking in performance, but as always, this depends a lot on the characteristics of your data, so please make your own tests. I have some performance graphs here (you may need to download it, GitHub takes ages to display it).