<p>Ok, things look pretty good to me.  As for the refactoring, we can do that after spill trees are merged.</p>

<p>I ran timing simulations, and as expected, the RP tree is slower than the kd-tree (after all it has looser bounds in all cases).  I only have one remaining question and then a few observations.</p>

<ul>
<li><p>Should we use RPMax as the default?  Nearly all of my simulations indicate that it performs better than RPMean.</p></li>
<li><p>The random projection tree appears to do almost as well as the kd-tree in higher dimensions; for instance, performance is almost the same on the MNIST dataset.  I wonder if there exist datasets where it may outperform the kd-tree.</p></li>
<li><p>The results of one of Pari's papers (<a href="http://papers.nips.cc/paper/5121-which-space-partitioning-tree-to-use-for-search">http://papers.nips.cc/paper/5121-which-space-partitioning-tree-to-use-for-search</a>) compares random projection trees, kd-trees, and some other types of trees for defeatist search.  Pari's results indicate that the rp-tree is generally the worst-performing of the tree types that he tried.  I wonder if we will see the same results in our own surveys for defeatist search.</p></li>
</ul>

<p>I am not sure, in the end, how effective the random projection tree will be, but I think that it is good to have it implemented.  It seems there are not many studies of its empirical effectiveness (if you know of any, send some links!  I would be interested to read).</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/726#issuecomment-240268981">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFA1zHVDh119k0FetvzT74bD17G--ks5qgkVpgaJpZM4JOuGE">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFGA4qEl0mxvLai1eU8EWnDuD65Muks5qgkVpgaJpZM4JOuGE.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/726#issuecomment-240268981"></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 #726: Ok, things look pretty good to me.  As for the refactoring, we can do that after spill trees are merged.\r\n\r\nI ran timing simulations, and as expected, the RP tree is slower than the kd-tree (after all it has looser bounds in all cases).  I only have one remaining question and then a few observations.\r\n\r\n * Should we use RPMax as the default?  Nearly all of my simulations indicate that it performs better than RPMean.\r\n\r\n * The random projection tree appears to do almost as well as the kd-tree in higher dimensions; for instance, performance is almost the same on the MNIST dataset.  I wonder if there exist datasets where it may outperform the kd-tree.\r\n\r\n * The results of one of Pari's papers (http://papers.nips.cc/paper/5121-which-space-partitioning-tree-to-use-for-search) compares random projection trees, kd-trees, and some other types of trees for defeatist search.  Pari's results indicate that the rp-tree is generally the worst-performing of the tree types that he tried.  I wonder if we will see the same results in our own surveys for defeatist search.\r\n\r\nI am not sure, in the end, how effective the random projection tree will be, but I think that it is good to have it implemented.  It seems there are not many studies of its empirical effectiveness (if you know of any, send some links!  I would be interested to read)."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/726#issuecomment-240268981"}}}</script>