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

[Ryan Curtin]

The reason that we are seeing no change between the bounds is because the modifications to B_2() actually never comes into play in the current traversals that we have.  As you pointed out, for kd-trees and ball trees and any other tree that only holds points in the leaves, rho(N_q) = lambda(N_q) so there is no problem.  But for cover trees, the traversal is somewhat odd: it is depth-first in the query points and breadth-first in the references.  This, along with the structure of the tree, means that for any query node N_q, we visit some set of reference nodes before any node combinations containing a descendant of N_q are visited, and then we never visit a node combination with N_q again.  (I hope that explanation makes sense.)  Therefore, B_aux actually goes unused, as does the part of B_2 that concerns child nodes, because no distances have been calculated for any descendant points of N_q except the one point held by N_q (which will give the tightest bound for B_2).

So, I am tempted to say that we shouldn't change anything here: it is already working as-is; the problem you pointed out (which is a valid problem) doesn't actually surface in the code that we have.  The modifications you made, while correct, do slow down the calculation a bit, by making `NeighborSearchStat` larger.  I think a better way to go, and maybe this is not feasible for right now, is to use `TreeTraits` (or maybe a new `TraversalTraits`) to determine which bounding strategies are valid for which types of trees and traversals.  Then we can simply avoid calculating certain bounds in certain cases.

What do you think?  I guess it's not a problem to merge in the changes you made, with the hope of coming up with a cleaner set of bounds sometime later.

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