n2a icon indicating copy to clipboard operation
n2a copied to clipboard

Incremental update of kd-tree

Open frothga opened this issue 6 years ago • 0 comments

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.

frothga avatar Feb 06 '19 23:02 frothga