search

KristofferC / NearestNeighbors.jl

High performance nearest neighbor data structures (KDTree and BallTree) and algorithms for Julia.
Other
413 stars 65 forks source link

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

Closed knrumsey-lanl closed 1 year ago

knrumsey-lanl commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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?