User talk:Duyn/kd-tree Tutorial

Interesting work here. Personally I'd consider such a code-heavy tutorial to be more of a 'code-explanation' than a tutorial, but still very good. Also, pretty good job optimizing fairly well there :) --Rednaxela 16:07, 27 February 2010 (UTC)

Also, I'd say that the 'Bounds-overlap-ball check' optimization is probably one of the most important things in how this tree benchmarks well. I also find it interesting how that optimization is in that paper, I've never seen it mentioned before in texts on kd-trees. However when I implemented that type of check in my own kd-tree, it just came to mind to do in a "... why hasn't anyone else done this? It seems so obvious" type of moment. You may be interested in one detail of how I was doing it differently though. I didn't use those bounds checking for the path order, I just used the conventional method based on the split. In addition, I only do did the 'bounds-overlap-ball check' for evaluating if 'second choice' branches are worthwhile. The reason for this is that:

1. Bounds checks are expensive
2. The 'first choice' branch to descend is very likely to have what we're looking for since it's parent branch was either a 'first choice' branch or had the bounds check done on it.

Benchmarks showed that those effect were significant enough that the detailed bounds check was only worthwhile in pruning needless 'second choice' branches. I'm curious if your implementation would show similar results if it skipped the bounds chck in those circumstances. --Rednaxela 01:43, 28 February 2010 (UTC)

Thank you for the suggestion. I have tried it, but found it didn't make a significant impact on the performance of the tree:

...[snip]...

RESULT << k-nearest neighbours search with duyn's Bucket kd-tree >>
: Average searching time       = 0.078 miliseconds
: Average worst searching time = 17.077 miliseconds
: Average adding time          = 2.49 microseconds
: Accuracy                     = 100%

...[snip]...

BEST RESULT: 
 - #1 Rednaxela's Bucket kd-tree [0.0536]
 - #2 duyn's Bucket kd-tree [0.0777]
 - #3 Simonton's Bucket PR k-d tree [0.1625]
 - #4 Voidious' Bucket PR k-d tree [0.2203]
 - #5 Nat's Bucket PR k-d tree [0.3654]
 - #6 Voidious' Linear search [0.5836]

Benchmark running time: 554.32 seconds

Although these results are perilously close to the rounding edge, it works out to a gain on previous performance of:

   <math>{0.0787 - 0.0777 \over 0.0787} = 1.27\%\ \mathrm{improvement}</math>

Profiling with netbeans indicates it is the search() and searchXXX() functions, not the distance/bounds calculations which are slowing the tree most. This suggests that:

• the tree's balance is not optimal so we have to search a lot of trees;
• the regions are not very square so our search hypersphere overlaps with a lot of hyperrects;
• using a TreeMap for collecting results is slow; or
• there is little more to gain without another theoretic insight.—duyn 04:41, 28 February 2010 (UTC)