<p>I have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.</p>

<p>I have a concern<br>
I have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.</p>

<p>I like the way that you have managed to reuse so much code.  To this point I have only really reviewed the <code>SpillTree</code> class and <code>SpillSearch</code> class, so I still have much to look at.  But there is a big issue I think we should address:</p>

<p>If we use mlpack's existing single-tree and dual-tree traversers, then the process at each node looks like this (invariably):</p>

<ol>
<li>Score each node.</li>
<li>Recurse into those nodes that have not been pruned.</li>
</ol>

<p>So this means for defeatist search, even with spill trees, we are doing the following:</p>

<ol>
<li>Calculate left score (0 or DBL_MAX).</li>
<li>Calculate right score (0 or DBL_MAX).</li>
<li>Recurse into the direction whose score is 0.</li>
</ol>

<p>Since calculations 1 and 2 are separate, we are projecting the query point (or query node) onto the splitting hyperplane's normal vector twice.  But that's twice as much work as we need to do.  Instead, we would be better off if we implemented some function <code>GetNearestChild()</code> (or something similar), and then did not use the traversers at all for defeatist search, but instead inside of <code>Search()</code>, something more like calling <code>GetNearestChild()</code> and then proceeding in the direction of that child only, until the current node is a leaf.  Dual-tree search might be a bit more tricky but still definitely possible.</p>

<p>What do you think?  I think that could accelerate the runtime of defeatist search significantly.  If you agree with the idea, then we can keep discussing details, but there is no need until we get to that point, I think. :)</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/747#issuecomment-237901505">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFFiCX_X-ZzL84JRb_hew8-Xw4xptks5qc2jmgaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFFc2tn9f_13hYQIphSuXBMachzeNks5qc2jmgaJpZM4JZzLU.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/747#issuecomment-237901505"></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://assets-cdn.github.com/images/modules/aws/aws-bg.jpg","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 #747: I have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.\r\n\r\nI have a concern\r\nI have no idea about the AppVeyor failure; maybe it is an MSVC bug?  It seems like maybe there is some issue with template aliases.\r\n\r\nI like the way that you have managed to reuse so much code.  To this point I have only really reviewed the `SpillTree` class and `SpillSearch` class, so I still have much to look at.  But there is a big issue I think we should address:\r\n\r\nIf we use mlpack's existing single-tree and dual-tree traversers, then the process at each node looks like this (invariably):\r\n\r\n 1. Score each node.\r\n 2. Recurse into those nodes that have not been pruned.\r\n\r\nSo this means for defeatist search, even with spill trees, we are doing the following:\r\n\r\n 1. Calculate left score (0 or DBL_MAX).\r\n 2. Calculate right score (0 or DBL_MAX).\r\n 3. Recurse into the direction whose score is 0.\r\n\r\nSince calculations 1 and 2 are separate, we are projecting the query point (or query node) onto the splitting hyperplane's normal vector twice.  But that's twice as much work as we need to do.  Instead, we would be better off if we implemented some function `GetNearestChild()` (or something similar), and then did not use the traversers at all for defeatist search, but instead inside of `Search()`, something more like calling `GetNearestChild()` and then proceeding in the direction of that child only, until the current node is a leaf.  Dual-tree search might be a bit more tricky but still definitely possible.\r\n\r\nWhat do you think?  I think that could accelerate the runtime of defeatist search significantly.  If you agree with the idea, then we can keep discussing details, but there is no need until we get to that point, I think. :)"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747#issuecomment-237901505"}}}</script>