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

[MarcosPividori]

Hi Ryan,
Thanks for your reply. Ok, I agree with you.
I think It would be important to fix this and analyze performance before concentrating on aprox. nearest neighbor, because we need to work over this code indeed. So, if you agree, I would like to work on this!
I can see that now we accept these different tree options for Neighbor Search:
 - KDTree (default)
 - R-Tree
 - R*Tree
 - X-Tree
 - CoverTree
 - BallTree

Actual KDTree implementation doesn't not show any problem because points are only included in leaf nodes, so the optimization of using rho instead of lambda is never considered. The value of the original B_2 bound and the modification to use B_{aux} will be the same. So, we will have exactly the same number of BaseCases.
The same applies to R-Trees/R*-Trees/X-Trees (as far as I understand, they don't include points in non-leaf nodes), and for BallTrees too.

CoverTrees are the interesting case. They include a point in each non-leaf node.
So, if we change actual B_2 implementation to use B_{aux}, we will have a less tight bound, which will probably result in more BaseCases.
However, we know the original B2 bound is correct for trees that consider ball bounds, as you have proved before.

So, if you agree, I can do this:
+ Implement the modification to use B_{aux}.
+ Compare the performance after this modification with previous implementation.
  We shouldn't see any difference for all trees except for cover trees.
+ If the difference is relevant, we can modify the code to use previous B2 bound only when it is safe to do that. For example, we could add a new field in TreeTraits to decide.

---
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-222325235
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160528/8acc997d/attachment.html>