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

MarcosPividori notifications at github.com
Thu Aug 4 12:40:33 EDT 2016


Hi @sumedhghaisas! I have implemented generalized Spill Trees, to consider general splitting hyperplanes, not necessarily axis-orthogonal.

I added a new template parameter for Spill Trees: `HyperplaneType`, and I implemented two candidate classes: `AxisOrthogonalHyperplane` and `Hyperplane`.
+ `AxisOrthogonalHyperplane` consider an axis-parallel projection vector. So, we can project any vector in O(1) time, considering the appropiate dimension.
+ `Hyperplane` consider a general projection vector. So we can project any vector in O(d) time, through a dot product.

Inside the SpillTrees, I consider BallBound for non-axis-orthogonal hyperplanes, and HrectBound for axis-orthogonal hyperplanes.
Also, I replaced the methods: SplitValue() and SplitDimension() by HalfSpaceContains() and HalfSpaceIntersects(), which are more general.

Considering this abstraction, I managed to significantly simplify the Split methods: MeanSplit and Midpoint Split. Now, they share most of the code.

I think we could use this abstraction for BinarySpaceTrees too.

By default, SpillSearch considers `AxisOrthogonalHyperplanes` because they seem to be faster in many cases, but this is not always true. I think we should benchmark both methods and see which is faster and which is more accurate, I mean, which has the best relation between running time and relative approximation error.

I will add a new command line flag "--get_real_error" to compare the approximate neighbor search against the naive method and print the real relative error, so we can benchmark with different values of tau and different spill tree flavours.

Thanks,

Marcos


---
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-237610583
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160804/0a0e9e9c/attachment.html>


More information about the mlpack-git mailing list