[mlpack-git] (blog) master: Lozhnikov, week 9. (53e0efa)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/blog
On branch  : master
Link       : https://github.com/mlpack/blog/compare/cdd30ef93550fa8bdac651b7f57ff588dc515535...53e0efa7a171c6f35dbc6c469632f30975c1e87a

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

commit 53e0efa7a171c6f35dbc6c469632f30975c1e87a
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Wed Jul 27 00:34:49 2016 +0300

    Lozhnikov, week 9.


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

53e0efa7a171c6f35dbc6c469632f30975c1e87a
 content/blog/LozhnikovWeekNine.md | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/content/blog/LozhnikovWeekNine.md b/content/blog/LozhnikovWeekNine.md
new file mode 100644
index 0000000..f81046f
--- /dev/null
+++ b/content/blog/LozhnikovWeekNine.md
@@ -0,0 +1,14 @@
+Title: Implementation of tree types : Week 9
+Date: 2016-07-27 00:30:00
+Tags: gsoc, space trees, Vantage point tree, UB-tree
+Author: Mikhail Lozhnikov
+
+Last week I have been working on the vantage point tree and the universal B-tree.
+
+### Vantage point tree
+I tried various fixes of the vantage point tree. Namely, I moved vantage points to separate nodes. That should considerably simplify pruning rules (we needn't implement the score algorithm for a query node and a reference point). Thus, each intermediate node of the vantage point tree contains three children. The first child contains only the vantage point. In such a way, the first point of the first sibling of a node is the centroid of the node.
+
+This property allows to use some optimizations in dual-tree algorithms and I added this check to `NeighborSearchRules` and `RangeSearchRules`. There are still some errors, some base cases are duplicated.
+
+### Universal B-tree
+The UB-tree is a variant of the B-tree. It introduces an ordering in multidimensional space i.e. the space is mapped to a linear ordered space. Notably, this mapping preserves the multidimensional clustering. Thus, all points are inserted into the UB-tree according to this ordering. I implemented the split algorithm. Right now, I am working on the implementation of the UB-tree bound. This bound is slightly more complicated than `HRectBound` since it consists of a number of hyperrectangles. In contrast to `VantagaPointTree`, this bound preserves a crutial property of `BinarySpaceTree`. Namely, UB-tree's children do not overlap each other.