[Question] Can you insert new data into an existing KDTree object?

[knrumsey-lanl]

I am building a KDTree object and using it to find the nearest neighbors for several points. Sometime later, suppose that I want to insert new points into my existing KDTree, which should be a log(n) operation. It seems that to do this, I have to just recreate a new KDTree with the appended data, which is a n*log(n) operation. It would be nice to have an insert!(kdtree, new_point) function. Does this functionality exist? If not, can it be added?

using NearestNeighbors
data = rand(3, 10^4)
kdtree = KDTree(data)

point = rand(3)
idxs, dists = knn(kdtree, point, k, true)

new_data_point = rand(3)
# Seems like I have to do this...
kdtree = KDTTree([data new_data_point])
# But I would rather do this...
# insert!(kdtree, new_point)

idxs, dists = knn(kdtree, point, k, true)

[KristofferC]

It does not exist and it is unlikely that it will be added to this package since many optimizations and layout decisions are done based on the number of points in the initial set of points.

As written in the docs:

All trees in NearestNeighbors.jl are static which means that points can not be added or removed from an already created tree.

[knrumsey-lanl]

Do you believe it is possible, with moderate to low effort, to modify the code myself so that an insert!() function can be written in a way that is faster than rebuilding the full tree each time?