[mlpack-git] [mlpack/mlpack] Neighbor Search - Incorrect bound. (#642)

Ryan Curtin notifications at github.com
Tue May 31 16:06:12 EDT 2016


We could avoid the difference for cover trees if we refactored the bound like this:

* Add `HasBallBound()` to `TreeTraits`; this is true for the ball tree and the cover tree but none of the other trees we currently have implemented.
* When `TreeTraits<TreeType>::HasBallBound()` is true, we use the existing adjusted point bound of D_p[k] + rho(N_q) + lambda(N_q)
* Otherwise, we use the correct point bound for non-ball-bounds of D_p[k] + 2 lambda(N_q)

This is still the same bound as in the original paper for ball-bound trees, but it is the fixed looser bound for hyperrectangle (and other weird) trees.

I like the elegant solution in B_aux of not applying the adjustment until the highest level, instead of applying the adjustment at every level like in the current B_2 definition.  But I didn't see an easy way to not apply the adjustment until the highest level if we are considering a tighter bound when ball trees are used.

This should give the exact same performance as the existing implementation, so as long as we test that it's the same on one or two datasets there is no need for a big test on lots of datasets, I think.  What do you think?  Have I overlooked something (again)? :)

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/issues/642#issuecomment-222803954
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160531/979eb8df/attachment-0001.html>


More information about the mlpack-git mailing list