[mlpack-git] [mlpack/mlpack] Spill trees (#747)

[Ryan Curtin]

I have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.

I have a concern
I have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.

I like the way that you have managed to reuse so much code.  To this point I have only really reviewed the `SpillTree` class and `SpillSearch` class, so I still have much to look at.  But there is a big issue I think we should address:

If we use mlpack's existing single-tree and dual-tree traversers, then the process at each node looks like this (invariably):

 1. Score each node.
 2. Recurse into those nodes that have not been pruned.

So this means for defeatist search, even with spill trees, we are doing the following:

 1. Calculate left score (0 or DBL_MAX).
 2. Calculate right score (0 or DBL_MAX).
 3. Recurse into the direction whose score is 0.

Since calculations 1 and 2 are separate, we are projecting the query point (or query node) onto the splitting hyperplane's normal vector twice.  But that's twice as much work as we need to do.  Instead, we would be better off if we implemented some function `GetNearestChild()` (or something similar), and then did not use the traversers at all for defeatist search, but instead inside of `Search()`, something more like calling `GetNearestChild()` and then proceeding in the direction of that child only, until the current node is a leaf.  Dual-tree search might be a bit more tricky but still definitely possible.

What do you think?  I think that could accelerate the runtime of defeatist search significantly.  If you agree with the idea, then we can keep discussing details, but there is no need until we get to that point, I think. :)

---
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/pull/747#issuecomment-237901505
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160805/5bca92bd/attachment.html>