[mlpack-git] (blog) master: Lozhnikov, week 10. (0d5896c)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/blog
On branch  : master
Link       : https://github.com/mlpack/blog/compare/e7947e665f45ac7e2a4bae24cbee7110a98fe7dc...0d5896c23a70a7d20d8d030ecc19c38e90bf866e

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

commit 0d5896c23a70a7d20d8d030ecc19c38e90bf866e
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Wed Aug 3 17:19:49 2016 +0300

    Lozhnikov, week 10.


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

0d5896c23a70a7d20d8d030ecc19c38e90bf866e
 content/blog/LozhnikovWeekTen.md | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/content/blog/LozhnikovWeekTen.md b/content/blog/LozhnikovWeekTen.md
new file mode 100644
index 0000000..8fe6961
--- /dev/null
+++ b/content/blog/LozhnikovWeekTen.md
@@ -0,0 +1,14 @@
+Title: Implementation of tree types : Week 10
+Date: 2016-08-03 17:15:00
+Tags: gsoc, space trees, UB-tree
+Author: Mikhail Lozhnikov
+
+Last week I have been working on the universal B tree. I finished the implementation of the bound and wrote a series of tests.
+
+In order to explain what the bound is I have to introduce the notions $\textbf{area}$ and $\textbf{address}$.
+
+An $\textbf{address}\ \alpha$ for an $\textbf{area}$ in an $n$-dimensional cube is a sequence $i_1.i_2.\ldots.i_l$, where $i_j\in \{1,2,\ldots,2^n\}$.
+
+I'll define the notion $\textbf{area}$ recursively. Let $\alpha$ be an $\textbf{address}$ for an $\textbf{area}$ in an $n$-dimensional cube `C` ($\textbf{area}(C)$). Partition `C` into $2^n$ subcubes $sc(i),\ i=1,2,\ldots,2^n$ by dividing `C` in the middle of each dimension. If $\alpha=k$ then $\textbf{area}(C)[k]=\bigcup_{i=1}^{k}sc(i),\ k=0,1,\ldots,2^n-1$. If $\alpha=k.\beta$ then $\textbf{area}(C)[\alpha]=\textbf{area}(C)[k]\cup \textbf{area}(sc(k+1))[\beta]$, where $\textbf{area}(sc(k+1))[\beta]$ is an area in $sc(k+1)$.
+
+Each child node of the universal B tree is bounded by two addresses i.e. the bound of a node is the difference of two areas. Since I deal with floating point numbers I use fixed-sized addresses in the whole space. The calculation of the distance between two nodes requires a lot of arithmetic operations. So, I decided to restrict the number of steps in the bound. Thus, children may overlap each other.