search

ubilabs / kd-tree-javascript

JavaScript k-d Tree Implementation
MIT License
642 stars 109 forks source link

Add functions to insert and remove elements after the tree has been created #1

Closed Robdr closed 12 years ago

Robdr commented 12 years ago

I'm looking to us a KD-tree for spatial clustering of markers on Node.js. For this the KD-tree would need to support inserting and removing elements after it has been created because it needs to be uopdated when markers are either removed from or inserted to the database.

Thanks, Rob

mirceapricop commented 12 years ago

We could work on that, but inserting and removing nodes can lead to unbalanced trees which can hurt the speed of operations on them.

A solution to that would be to either maintain a balanced tree at all times (very hard because of the different splitting dimensions), or to provide a way for you to measure how unbalanced the tree is and rebuild it if it crosses a threshold.

Would the second option be good enough?

Robdr commented 12 years ago

The second option would definitely work on my end. Updates will be relatively infrequent in my case.

mirceapricop commented 12 years ago

How would specifying nodes for deletion go?

We're thinking either by deleting the first node equal in all dimensions to the query. Deleting by reference would also work, but then you'd have to store them outside the tree too.

Robdr commented 12 years ago

In my case there might be nodes that have the same dimensions (additionally they have a globally unqiue ID as well). So deleting by reference would work best for me.

prabhasp commented 12 years ago

@ubilabs thanks for the kdtree; its quite helpful. want to second the usefulness of delete by reference.

mirceapricop commented 12 years ago

Mutable trees have landed! Check out the new example, test it out and report any bugs that you find.

Closing the issue for now.