Incremental creation of KD-TREE

[karry3775]

Hi, I wanted to know if there is a way to incrementally add points to the kd-tree, like say one at a time. What I basically want to achieve is run the kd-tree generation inside a loop so that the tree expands every time it receives a new element. Thanks!

[tommasocarella]

Hi @karry3775 ! Did you find any way to implement this? I was thinking of using the KDTreeSingleIndexDynamicAdaptor which presents methods for addition and removal of points. Did you find a better way?

[karry3775]

Unfortunately, I am not using that feature for now, so stopped looking into it. You can close the issue and reopen later if need be.

On Sat, Mar 20, 2021 at 3:41 PM Yash Bansod @.***> wrote:

@karry3775 https://github.com/karry3775, @tommasocarella https://github.com/tommasocarella, did you find a good way of doing this? I want to do a similar thing for adding nodes to the NN in my tree incrementally.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/jlblancoc/nanoflann/issues/139#issuecomment-803453011, or unsubscribe https://github.com/notifications/unsubscribe-auth/AKLHQTYXH7V6BN7RDDXH5T3TET25ZANCNFSM4U3RAY6A .

[dschwen]

KDTreeSingleIndexDynamicAdaptor seems to create a "forrest" of kd-trees. Every point set addition creates a new tree. When searching, each tree needs to be queried for a consolidated result. This will increase lookup times. Looks like depending on frequency of insertion vs. frequency of lookups, when you get to a certain number of sub-trees it might be beneficial to re-index all points as a new tree to improve lookup performance again.