<p>I see what you mean about the problems of the UB tree, now that I have read the paper.  In essence the idea of mapping the space to addresses, and each address representing a subregion, means that if we have only two points that are adjacent in some dimension d, but the difference in the addresses is high, then the node enclosing both of those encloses a huge amount of empty space!  So, even if we do optimize this tree like crazy, I am not sure we will be able to produce something that is competitive with the kd-tree, at least for the task of nearest neighbor search.  Perhaps it will be more useful for something like range search or other tasks.</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-240561544">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFHn3fjdSLchQ3WEh5jmgRkt0sDP3ks5qg4NegaJpZM4JZrEi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFAThVUk722_bqv167NJtI0b2Qx3Iks5qg4NegaJpZM4JZrEi.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-240561544"></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 see what you mean about the problems of the UB tree, now that I have read the paper.  In essence the idea of mapping the space to addresses, and each address representing a subregion, means that if we have only two points that are adjacent in some dimension d, but the difference in the addresses is high, then the node enclosing both of those encloses a huge amount of empty space!  So, even if we do optimize this tree like crazy, I am not sure we will be able to produce something that is competitive with the kd-tree, at least for the task of nearest neighbor search.  Perhaps it will be more useful for something like range search or other tasks."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/746#issuecomment-240561544"}}}</script>