<p>This might be a clue to the performance issue.  I modified the code to print information on the bounds and distances for single-tree search.  Here's what I see on the first node of the tree, for query point 0 (with the corel dataset, but you could reproduce these results with probably any dataset):</p>

<pre><code>[DEBUG] MinDistance() with inner radius 0, outer radius 8.48376 and center distance 0 (innerDistance 0, outerDistance 0).
[INFO ] Score query index 0 and reference node 1c20746 (child 1): 0 vs. bound 1.79769e+308.
[DEBUG] MinDistance() with inner radius 0, outer radius 13.8071 and center distance 0 (innerDistance 0, outerDistance 0).
[INFO ] Score query index 0 and reference node 20747c17002 (child 2): 0 vs. bound 1.79769e+308.
</code></pre>

<p>It's expected that neither the first inner child nor the first outer child should be pruned.  But what's not expected is that my code in <code>HollowBallBound</code> (the <code>[DEBUG]</code> message) is reporting that the inner radius of the outer child is 0!  Maybe there is some bug where that value is calculated?</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/708#issuecomment-235101060">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFDu02dFsS5gHhWIelFzmq0ORhld5ks5qZTOZgaJpZM4I_COp">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFMzGXp6rgZGAQxBTyqKCcWom0RFVks5qZTOZgaJpZM4I_COp.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/708#issuecomment-235101060"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>