Rolling KD-Tree?

Jump to navigation Jump to search

Rolling KD-Tree?

So I am trying to work out how you deal with rolling averages in a KD-Tree DC gun implementation? I'd like a low rolling average anti-surfer gun. Silly question but I have no idea how to do it. I understand you can use time as a dimension in the tree, but then there is the problem of distance. Time is a continuous variable, which means you can't just go "get me the last 3 Guess Factors that match the current situation" as the time dimension in the tree will mean that you are not guaranteed the latest? I'm probably not explaining it very well. If you weight the time the same as other dimensions then you might get recent values, but, given the weighting of time in a 0-1 value distance matching, pulling 3 values out of the tree will not necessarily give you the 3 latest values, just the 3 closest values which might match latest or might be closer in non-time values?

This is a pretty terrible explanation/question sorry, but I'm trying to understand how to integrate low rolling averages with DC.

If you don't put time as a dimension and just pull out the say, 100 closest matches, you are not necessarily going to get any recent matches, so even if you put time-stamps in the data to filter those 100 results, you might not get any at all which are recent?

Wolfman (talk)10:57, 7 August 2021

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)21: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)06:34, 8 August 2021