<p>The UB tree has two problems.</p>

<p>The bound of the tree is not the tightest since the tightest bound requires a lot of computations in <code>MinDistance()</code>. That can explain that the number of base cases with the kd tree is less than the number of base cases with the UB tree.</p>

<p>And the second problem is the performance of <code>MinDistance()</code>. The function calculates the distance to a number of hyperrectangles. I believe that many of them may be pruned but I do not know exactly how.</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/746#issuecomment-240361014">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFDo9aaNfjQayksAAJQCtGFqiA1h3ks5qgtRigaJpZM4JZrEi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFF05Nf8XRyJOoEW0eXBehVOD6sFsks5qgtRigaJpZM4JZrEi.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/746#issuecomment-240361014"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>

<script type="application/json" data-scope="inboxmarkup">{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/mlpack/mlpack","title":"mlpack/mlpack","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/mlpack/mlpack"}},"updates":{"snippets":[{"icon":"PERSON","message":"@lozhnikov in #746: The UB tree has two problems.\r\n\r\nThe bound of the tree is not the tightest since the tightest bound requires a lot of computations in `MinDistance()`. That can explain that the number of base cases with the kd tree is less than the number of base cases with the UB tree.\r\n\r\nAnd the second problem is the performance of `MinDistance()`. The function calculates the distance to a number of hyperrectangles. I believe that many of them may be pruned but I do not know exactly how."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/746#issuecomment-240361014"}}}</script>