<p>I need to review the paper before I can make more comments, but I am surprised that this is so much slower than the kd-tree.  I am seeing performance about the same as the rp-tree.  To me this seems odd.  I can understand why the vp-tree is slow and I can understand why the rp-tree (and variants) are slow, and I know that the R tree and its variants will also be slow as compared to the kd-tree, but I had thought that the ub-tree, since it was so similar with axis-aligned pretty-tight hyperrectangles, would be much faster.  Even with low-dimensional data, it often takes an order of magnitude more base cases.</p>

<p>When I am able to review the paper, maybe I will be able to reason if something is wrong.  A cursory inspection of the code to calculate the minimum and maximum distances seems fine, but the only hesitation I have is about whether or not the actual strategy of splitting points into bounds is correct.  (But again I have to refer to the paper before I can comment more there.)</p>

<p>Outside of that, the code quality seems great.</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-240315737">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFNZPZewrfhR3xWgOiSvvDSfv8vR8ks5qgplSgaJpZM4JZrEi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFCxTWWP0C3CR2tt2wc7J5cYhh_k4ks5qgplSgaJpZM4JZrEi.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-240315737"></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":"@rcurtin in #746: I need to review the paper before I can make more comments, but I am surprised that this is so much slower than the kd-tree.  I am seeing performance about the same as the rp-tree.  To me this seems odd.  I can understand why the vp-tree is slow and I can understand why the rp-tree (and variants) are slow, and I know that the R tree and its variants will also be slow as compared to the kd-tree, but I had thought that the ub-tree, since it was so similar with axis-aligned pretty-tight hyperrectangles, would be much faster.  Even with low-dimensional data, it often takes an order of magnitude more base cases.\r\n\r\nWhen I am able to review the paper, maybe I will be able to reason if something is wrong.  A cursory inspection of the code to calculate the minimum and maximum distances seems fine, but the only hesitation I have is about whether or not the actual strategy of splitting points into bounds is correct.  (But again I have to refer to the paper before I can comment more there.)\r\n\r\nOutside of that, the code quality seems great."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/746#issuecomment-240315737"}}}</script>