Thoughts area

test.html

<h2 id="r-tree">R*-tree</h2>

<p><a href="http://www.cs.ucr.edu/~tsotras/cs236/W15/rstar.pdf">Source article about R*-tree</a></p>



<h3 id="what-is-r-tree-actually">What is r-tree actually</h3>

<ul>
<li><script type="math/tex" id="MathJax-Element-1"> B^+ </script> tree like structure, which stores multidimensistrong textonal rectangles</li>
</ul>



<h4 id="non-leaf-node">Non-leaf node</h4>

<p>non-leaf node contains entries of the form</p>



<pre class="prettyprint"><code class="language-c++ hljs cs"><span class="hljs-keyword">var</span> childPointer, Rectangle</code></pre>

<p>where <em>childPointer</em> - is the address of a child node in the R-tree and <em>Rectangle</em> is the <a href="#mbr">minimum bounding rectangle</a> of all rectangles which are entries in that child node</p>



<h4 id="leaf-node">Leaf node</h4>

<p>leaf node contains entries of the form</p>



<pre class="prettyprint"><code class="language-c++ hljs cs"><span class="hljs-keyword">var</span> objectPointer, Rectangle</code></pre>

<p>where <em>objectPointer</em> refers to a record in some storage, describing a spatial object and <em>Rectangle</em> is the enclosing rectangle of that spatial object</p>

<p>Let <script type="math/tex" id="MathJax-Element-2"> M </script> be the maximum number of entries that will fit in one node, and let <script type="math/tex" id="MathJax-Element-3"> m </script> be a parameter specifying the minimum number of entries in a node <script type="math/tex" id="MathJax-Element-4"> ( 2 \leq m \leq \frac{M}{2} ) </script>. An R-tree satisfies the following properties:</p>

<ul>
<li>The root has at least two children unless it’s a leaf</li>
<li>Every non-leaf node has between <script type="math/tex" id="MathJax-Element-5"> m </script> and <script type="math/tex" id="MathJax-Element-6"> M </script> childrens unless it’s the root</li>
<li>Every leaf node contains between <script type="math/tex" id="MathJax-Element-7"> m </script> and <script type="math/tex" id="MathJax-Element-8"> M </script> entries unles it’s the root</li>
</ul>

<blockquote>
  <p>Notice, the words play here, <code>has</code> versus <code>contains</code>, first is actually having, and second is crossreferencing through childrens(i think).</p>
</blockquote>

<ul>
<li>All leaves appears on the same level</li>
</ul>



<h3 id="optimization-criterias">Optimization criterias</h3>

<ul>
<li><strong>(O1)</strong> <em>The area covered by a directory rectangle should be minimized</em></li>
<li><strong>(O2)</strong> <em>The overlap between directroy rectangles should be minimized</em>. </li>
<li><strong>(O3)</strong> <em>The margin of a directory rectangle should be minimized</em></li>
<li><strong>(O4)</strong> <em>Storage utilization should be optimized</em>. </li>
</ul>



<h3 id="r-tree-variants">R-tree variants</h3>

<p>The R-tree is a dynamic structure, thus all aproaches of optimizing the retrieval performance have to be applied during the insetion of a new data rectangle. The insetion algorithm calls two more algorithms in which the crucial decisions for good retrieval performance are made. The first is the algorithm <code>ChooseSubtree</code>. Beginning in the root, descending to a leaf, it finds on every level the most suitable subtre, to accomodate the new entry. The second is the algorithm <code>Split</code>, it is called, if <code>ChooseSubtree</code> ends in a node filled with the maximum number of entries <script type="math/tex" id="MathJax-Element-9"> M  </script>. <code>Split</code> should distribute <script type="math/tex" id="MathJax-Element-10">M + 1</script> rectangles into two nodes in the most appropriate manner.</p>



<h4 id="choosesubtree-algorithm">ChooseSubtree algorithm</h4>

<p>Let <script type="math/tex" id="MathJax-Element-11"> \{E_1, \dots, E_p\} </script> be the entries in the current node. Then <script type="math/tex" id="MathJax-Element-12"> \text{overlap}(E_k) = \sum\limits_{i=1, i \ne k}^p \text{area}(E_k \text{Rectangle} \cap E_i \text{Rectangle}) </script></p>



<pre class="prettyprint"><code class="language-c++ hljs r">bool is_root(Node node)
{
    <span class="hljs-keyword">return</span> node.childrens.count &gt;= <span class="hljs-number">2</span>;  // ?
}

bool is_leaf(Node node)
{
    node.childrens.count &gt;= m &amp;&amp; <span class="hljs-keyword">...</span> &lt;= M;
}</code></pre>

<p><strong>Algorithm ChooseSubtree</strong></p>



<pre class="prettyprint"><code class="language-bash hljs "><span class="hljs-number">1</span>: Set N to be the root
<span class="hljs-number">2</span>: <span class="hljs-keyword">if</span> N is a leaf,
    <span class="hljs-keyword">return</span> N
<span class="hljs-keyword">else</span>
    <span class="hljs-keyword">if</span> the childpointers <span class="hljs-keyword">in</span> N point to leaves [determine the minimum overlap cost],
    choose the entry <span class="hljs-keyword">in</span> N whose rectangle needs least overlap enlargement to include the new data rectangle. Resolve ties by choosing the entry whose rectangle needs least area enlargement,
<span class="hljs-keyword">then</span>
    the entry with the rectangle of smallest area <span class="hljs-keyword">if</span> the childpointers <span class="hljs-keyword">in</span> N does not point to leaves
<span class="hljs-keyword">if</span> the childpointers <span class="hljs-keyword">in</span> N does not point to leaves
    [determine the minimum area cost]
    choose the entry <span class="hljs-keyword">in</span> N whose rectangle need least area enlargement to include the new data rectangle. Resolve ties by choosing the entry with the rectangle of smallest area
end

<span class="hljs-number">3</span>: Set N to be the childnode pointed to by the childpointer of the chose entry and repeat from <span class="hljs-number">2</span>:</code></pre>

<p><a></a> <br>
<strong><em>Minimal Bounding Rectangle</em></strong> - The minimum bounding rectangle (MBR), also known as bounding box or envelope, is an expression of the maximum extents of a 2-dimensional object (e.g. point, line, polygon) or set of objects within its (or their) 2-D (x, y) coordinate system, in other words min(x), max(x), min(y), max(y). The MBR is a 2-dimensional case of the minimum bounding box. <br>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Minimum_bounding_rectangle.svg/220px-Minimum_bounding_rectangle.svg.png" alt="A series of geometric shapes enclosed by its minimum bounding rectangle" title=""></p>

<p><a></a> <br>
<strong><em>Directory Rectangle</em></strong> - geometrically is the minimum bounding rectangle of the underlying rectangles</p>

<p><a></a> <br>
<strong><em>Dead Space</em></strong> - Area covered by the bounding rectangle, but not covered by the enclosed rectangle</p>