<p>In <a href="https://github.com/mlpack/mlpack/pull/684#discussion_r66630184">src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp</a>:</p>
<pre style='color:#555'>&gt; @@ -419,6 +423,8 @@ inline double NeighborSearchRules&lt;SortPolicy, MetricType, TreeType&gt;::
&gt;    queryNode.Stat().SecondBound() = bestDistance;
&gt;    queryNode.Stat().AuxBound() = auxDistance;
&gt;  
&gt; +  worstDistance = SortPolicy::Relax(worstDistance, epsilon);
</pre>
<p>We can only relax the B_1 bound (worst distance).  We can not change the B_2 bound (best distance).<br>
I will try to make this clear, let me know it this isn't:<br>
For B_1, we are considering the worst distance. <br>
For B_2, in KNN we are estimating an upper bound of the best distance for all descendants of a node N_q, based on the distance calculated for some descendants.<br>
For example in KNN, suppose that our estimation is based on the distance calculated from a descendant point <em>p_q</em> in DescendantsPoints(N_q) and the reference point p_r. I mean, B_2 bound was calculated doing triangulation, using: dist(p_q,p_r):<br>
  So B_2(N_q) = dist(p_q,p_r) + some triangulation...<br>
In exact KNN we don't have any problem when prunning if d_{min}(N_q,N_r) &gt; B_2(N_q) . We can be sure that for all p_s in Descendants(N_q), the combination (p_s , p_r) will be considered at some moment, because we know dist(p_s , p_r) &lt;= B_2(N_q).</p>

<p>On the other hand, when doing approximation, we can not relax the value to: 0.5  * B_2(N_q).<br>
For some p_s in Descendants(N_q), the combination (p_s , p_r) could be pruned before being considered. We can not assert that:  dist(p_s , p_r) &lt;= 0.5 * B_2(N_q).</p>

<p>If this is not clear, I could provide an example tree where approximation would fail.</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/pull/684/files/07879a2cc79b35b10d7fae687d6e27ad90a9f2d7#r66630184">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFOqC1PZOc_xd53gwob-hfbwTr29aks5qKX6zgaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFF-8MnbC_tPagvaqYeC0WKDN6wUcks5qKX6zgaJpZM4IvhJu.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/pull/684/files/07879a2cc79b35b10d7fae687d6e27ad90a9f2d7#r66630184"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>