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

[Ryan Curtin]

You are right, I failed to consider that it is possible that a child hyperrectangle's implicit bounding ball can lie not entirely withing the parent hyperrectangle's implicit bounding ball.  It's easy to rework the proof I wrote to be correct and that comes out with the error correction 2 \lambda(N_q) - \lambda(N_c) (that is, we are subtracting just one times the furthest descendant distance of N_c, not two), but this is a less tight bound that the idea you suggested with B_{aux}(.).  So I guess that I can conclude that my bound is incorrect and there isn't a better choice I can see than to go with your solution.  Thanks for pointing all of this out.

When you apply this bound, it would be interesting to see how much it helps performance; that could easily be tracked by running `mlpack_knn` with the `-v` option, and looking at the number of base cases on a handful of datasets before and after the change.  If you want to do this, feel free; if not, that's no issue, I'll do it. :)

---
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-222153406
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160527/e63ffb76/attachment-0001.html>