<p>Hi <a href="https://github.com/sumedhghaisas" class="user-mention">@sumedhghaisas</a> <a href="https://github.com/rcurtin" class="user-mention">@rcurtin</a>,</p>

<p>I have implemented Spill trees with axis-parallel splitting hyperplanes. I have made an effort to avoid duplicating existing code for neighbor search.</p>

<p>I created a new class <code>SpillSearch</code> that provides an interface similar to <code>NeighborSearch</code> but with an extension to properly set the tau parameter. It encapsulates an instance of <code>NeighborSearch</code>.</p>

<p>Also, I have implemented a new version of <code>NeighborSearchRules</code> specialized for Spill Trees, because I needed to modify the methods:</p>

<ul>
<li>
<code>Score()</code> to consider splitting hyperplanes for overlapping nodes.</li>
<li>
<code>CalculateBounds()</code> to ignore B_2 bound (we can not use B_2 bound for Spill Trees).</li>
</ul>

<h2>Single Tree Search:</h2>

<p>The <code>SingleTreeTraverser</code> is similar to the implementation for <code>BinarySpaceTree</code>.<br>
The difference is in the implementation of <code>NeighborSearchRules</code> for SpillTrees.<br>
When calculating the score of a query point and a reference node I consider 2 cases:</p>

<ul>
<li>If the reference node is non-overlapping, I calculate the score the same than before.</li>
<li>If the reference node is overlapping, I analyze the reference node's half space. If it contains the given query point, I return 0 (best score). Else, I return DBL_MAX (prune).</li>
</ul>

<h2>Dual Tree Search:</h2>

<p>The Query tree is built without overlapping.</p>

<p>When calculating the score of a query node and a reference node, I consider 2 cases:</p>

<ul>
<li>If the reference node is a non-overlapping node, I calculate the score the same as before.</li>
<li>If the reference node is a overlapping node, I analyze query node's bounding box. If it intersects the reference node's half space, I return 0 (best score). Else, I return DBL_MAX (prune).</li>
</ul>

<p>The <code>DualTreeTraverser</code> is slightly different to the implementation for <code>BinarySpaceTree</code>. When referenceNode is a overlapping node and we can't decide which child node to traverse, this means that queryNode is at both sides of the splitting hyperplane, we analyse the queryNode:</p>

<ul>
<li>If queryNode is a non-leaf node, I recurse down the query node.</li>
<li>If queryNode is a leaf node, I do single tree search for each point in the query node.</li>
</ul>

<p>The <code>DualTreeTraverser</code> is faster than the <code>SingleTreeTraverser</code>. Specially when the value of tau increases, because we will have more non-overlapping nodes which implies more time involved in backtracking.</p>

<p>The extension was incorporated to existing <em>mlpack_knn</em>. With actual implementation, we can use <em>"-t spill"</em> to consider spill trees and <em>"--tau 0.1"</em> to set different values for the overlapping size (default value is tau=0).</p>

<p>I have made a pull request with this implementation in: <a href="https://github.com/mlpack/mlpack/pull/747" class="issue-link js-issue-link" data-url="https://github.com/mlpack/mlpack/issues/747" data-id="168696245" data-error-text="Failed to load issue title" data-permission-text="Issue title is private">#747</a>.</p>

<p>If you agree, I plan to work next days in these topics:</p>

<ul>
<li>Implement another version of SpillTrees to consider non-axis-parallel hyperplanes, using <code>BallBound</code> instead of <code>HrectBound</code>, and holding a projection vector in each node.</li>
<li>Add a command line flag <em>"--get_real_error"</em> to compare the approximate neighbor search against the naive method and print the real relative error, so we can test with differents values of tau and see the difference.</li>
</ul>

<p>Every feedback is welcome! :)</p>

<p>Thanks</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/issues/728#issuecomment-236645481">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFGjydrKnlG_5_89_KbwJ5-Jolkjdks5qbinwgaJpZM4JQY7d">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFCcH6e06MF1_G8wzodRbyqFZXG9Zks5qbinwgaJpZM4JQY7d.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
  <link itemprop="url" href="https://github.com/mlpack/mlpack/issues/728#issuecomment-236645481"></link>
  <meta itemprop="name" content="View Issue"></meta>
</div>
<meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>