<p>We could avoid the difference for cover trees if we refactored the bound like this:</p>

<ul>
<li>Add <code>HasBallBound()</code> to <code>TreeTraits</code>; this is true for the ball tree and the cover tree but none of the other trees we currently have implemented.</li>
<li>When <code>TreeTraits&lt;TreeType&gt;::HasBallBound()</code> is true, we use the existing adjusted point bound of D_p[k] + rho(N_q) + lambda(N_q)</li>
<li>Otherwise, we use the correct point bound for non-ball-bounds of D_p[k] + 2 lambda(N_q)</li>
</ul>

<p>This is still the same bound as in the original paper for ball-bound trees, but it is the fixed looser bound for hyperrectangle (and other weird) trees.</p>

<p>I like the elegant solution in B_aux of not applying the adjustment until the highest level, instead of applying the adjustment at every level like in the current B_2 definition.  But I didn't see an easy way to not apply the adjustment until the highest level if we are considering a tighter bound when ball trees are used.</p>

<p>This should give the exact same performance as the existing implementation, so as long as we test that it's the same on one or two datasets there is no need for a big test on lots of datasets, I think.  What do you think?  Have I overlooked something (again)? :)</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/642#issuecomment-222803954">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFByhOahXkO8H2jRKhc5yONOdbBDzks5qHJS0gaJpZM4Iksxi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFGGCDbyo_XPcht2ltnQG23pX99xHks5qHJS0gaJpZM4Iksxi.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/642#issuecomment-222803954"></link>
  <meta itemprop="name" content="View Issue"></meta>
</div>
<meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>