Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incremental update of kd-tree #76

Open
frothga opened this issue Feb 6, 2019 · 0 comments
Open

Incremental update of kd-tree #76

frothga opened this issue Feb 6, 2019 · 0 comments

Comments

@frothga
Copy link
Collaborator

frothga commented Feb 6, 2019

Both Internal and C backends use kd-tree for connection processing. Currently, they rebuild the tree every time connections are scanned. If memory permits keeping the tree between cycles, a more efficient approach is:

  • For each entry, search up the tree for the nearest node that still contains the (possibly new) location. This could terminate with the current leaf node itself, if there has been no change. Then insert the entry back in the tree by searching for the correct leaf under the selected node.
  • For each tree node (in depth-first order), if it's branches have become imbalanced, rebuild the subtree starting at that node.

Another possible optimization is to keep all the leaf buckets in a single vector. This equates to sorting sublists in place. The nodes themselves will, of course, require a separate structure.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant