Rolling KD-Tree?

Jump to navigation Jump to search

You do not have permission to edit this page, for the following reasons:

  • The action you have requested is limited to users in the group: Users.
  • You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page.

Return to Thread:Talk:Rolling Averages/Rolling KD-Tree?/reply.

Hrm thanks Kev. I should have thought about 2. I didn't see any obvious way to remove points on the tree I'm using (Rednaxela) but it looks like it does support a max size! :facepalm how did I not notice that before? Sigh. Always the simple things!

Edit: Update, looks like the 2nd gen tree supports max size, but the 3rd gen tree, which I'm using only supports setting the bucket size and has no removal of old points. I'll have to check out other KD tree implementations to support limiting tree size.

Wolfman (talk)20:07, 7 August 2021

Adding point removal isn't hard, the hard thing is to keep the right tree structure, which I haven't seen in most implementation, which is necessary to keep the tree performant.

Removing a point is essentially:

  1. search it as normal.
  2. iterate through each of the bucket and erases it.
Xor (talk)05:34, 8 August 2021