<p>In <a href="https://github.com/mlpack/mlpack/pull/684#discussion_r66673933">src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp</a>:</p>
<pre style='color:#555'>> @@ -419,6 +423,8 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::
> queryNode.Stat().SecondBound() = bestDistance;
> queryNode.Stat().AuxBound() = auxDistance;
>
> + worstDistance = SortPolicy::Relax(worstDistance, epsilon);
</pre>
<p>Yes, so the issue here is that we can have situations where we end up with no candidates at all (or fewer than k candidates) for a particular query point, because we would be pruning based on a too-tight B_2. I think it is still possible to prune in this case, but there is a little extra trickery involved in order to handle that. Basically if we were pruning based on a too-tight B_2, we would need to go through the tree and, for any query nodes with descendant points that are missing neighbors, we could use the reference points that B_2 was calculated with as those missing neighbors. I haven't worked the math and am not in a position to do so at the moment, but I think it's right.</p>
<p>Implementing that would be somewhat complex, so, I am not sure if that's worth doing now.</p>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<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#r66673933">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFOl00IOv0ySgvVvwnGvKodvgkrzsks5qKcTQgaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFE5Cy2_R6ett3cnu_2RLlrUTtuweks5qKcTQgaJpZM4IvhJu.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#r66673933"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>