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:
- Bounds checks are expensive
- 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)
Ahh yeah. Well, I didn't expect a miraculous improvement, and that is pretty close to the rounding amount. I do seem to remember though from my tests that while the improvement was small it was unambiguous, and I'd expect it to matter increasingly as the tree becomes increasingly deep beyond what this test data does. I doubt the TreeMap is the issue. While I used a max-heap in mine, since it's theoretically fastest and my implementation is very good, I doubt it's used quite enough to be a issue in this case. If you're concerned about that though, perhaps test out replacing it with the max-heap from my tree as a test? About the regions and balance, that's quite possible. Hmm... this reminds me, I really should experiment making a tree with "incremental near neighbor search", which instead of searching for a fixed number of nearest neighbors gives an iterator. Also, I should probably experiment with automatic rebalancing parts by tracking depth since insertion is orders of magnitude faster than searches anyway... --Rednaxela 05:44, 28 February 2010 (UTC)
