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

[MarcosPividori]

@rcurtin  Thanks for your feedback! 

I implemented Hybrid Spill Search. It does:
 + backtracking in non-overlapping node.
 + defeatist search on overlapping nodes.

So, it is different to pure defeatist search.

Because of that, I think we should continue using the Tree Traversers for the implementation.

I agree that code could be improved to avoid calculating the score of both child nodes (which means calculating the projection 2 times). It can make a difference, especially with non axis-orthogonal splitting hyperplanes, because the projection takes O(d) time.

So, I can implement a new method as you suggested:  "GetNearestChild()" and use it when working with a overlapping node in the `SingleTreeTraverser` and `DualTreeTraverser`.

That method is not strictly necessary. We could avoid including a new method, implementing it in a simply way:
If I have a overlapping node I calculate the score of one child, and decide based on that score without calculating the score of the second child:
- If the score of the first child is `DBL_MAX`, I have to traverse the second child (its score is `0`).
- If the score of the first child is `0`, I have to traverse the first child (the score of the second child is `DBL_MAX`).

Also, we could implement a pure `DefeatistTreeTraverser`, for every kind of tree (not only spill trees) that always considers the score of all the child nodes, chose the one with the lowest score and doesn't do backtracking.

Thanks!

---
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-238137161
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160807/9538a056/attachment.html>