[mlpack-git] (blog) master: Blog post week 11. (cc7762f)

gitdub at mlpack.org gitdub at mlpack.org
Wed Aug 10 14:50:34 EDT 2016


Repository : https://github.com/mlpack/blog
On branch  : master
Link       : https://github.com/mlpack/blog/compare/8be88ce1b8524e97cb9703b236e8b105e7f31be6...cc7762f3b19a872f2ce12f72c4244116f91a81ce

>---------------------------------------------------------------

commit cc7762f3b19a872f2ce12f72c4244116f91a81ce
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Wed Aug 10 15:50:12 2016 -0300

    Blog post week 11.


>---------------------------------------------------------------

cc7762f3b19a872f2ce12f72c4244116f91a81ce
 content/blog/MarcosWeekEleven.md | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/content/blog/MarcosWeekEleven.md b/content/blog/MarcosWeekEleven.md
new file mode 100644
index 0000000..9ec5ce9
--- /dev/null
+++ b/content/blog/MarcosWeekEleven.md
@@ -0,0 +1,30 @@
+Title: Approximate Nearest Neighbor Search - Week 11
+Date: 2016-08-10 09:00:00
+Tags: gsoc, knn, spill-tree
+Author: Marcos Pividori
+
+Last week, 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 Spill Tree, I consider `BallBound` for non-axis-orthogonal hyperplanes, and `HrectBound` for axis-orthogonal hyperplanes.
+
+Considering this abstraction, I managed to significantly simplify the Split methods: `MeanSplit` and `MidpointSplit`. Now, they share most of the code.
+
+By default, `SpillSearch` considers `AxisOrthogonalHyperplanes` because they seem to be faster in many cases, but this is not always true. We have to 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.
+
+All of this changes were included in the pull request: [[1]](https://github.com/mlpack/mlpack/pull/747).
+
+I plan to work next days in these topics:
+
++) Add many test cases for all the code developed: `SpillTree` class, `SpillSearch` class, `Hyperplane` class, etc.
+
++) AppVeyor has shown some problems with the MSVC compiler, in the resolution of template parameters of alias templates, similar to an old issue: [2]. I have to fix it, probably including some extra definitions.
+
++) Check details in the Spill Tree's implementation.
+
+Follow the progress in: [[2]](https://github.com/MarcosPividori/mlpack/tree/spill-trees/src/mlpack/core/tree/spill_tree).




More information about the mlpack-git mailing list