<p><a href="https://github.com/rcurtin" class="user-mention">@rcurtin</a>  Thanks for your feedback! </p>

<p>I implemented Hybrid Spill Search. It does:</p>

<ul>
<li>backtracking in non-overlapping node.</li>
<li>defeatist search on overlapping nodes.</li>
</ul>

<p>So, it is different to pure defeatist search.</p>

<p>Because of that, I think we should continue using the Tree Traversers for the implementation.</p>

<p>I agree that code could be improved to avoid calculating the score of both child nodes (which means calculating the projection 2 times). It can make a difference, especially with non axis-orthogonal splitting hyperplanes, because the projection takes O(d) time.</p>

<p>So, I can implement a new method as you suggested:  "GetNearestChild()" and use it when working with a overlapping node in the <code>SingleTreeTraverser</code> and <code>DualTreeTraverser</code>.</p>

<p>That method is not strictly necessary. We could avoid including a new method, implementing it in a simply way:<br>
If I have a overlapping node I calculate the score of one child, and decide based on that score without calculating the score of the second child:</p>

<ul>
<li>If the score of the first child is <code>DBL_MAX</code>, I have to traverse the second child (its score is <code>0</code>).</li>
<li>If the score of the first child is <code>0</code>, I have to traverse the first child (the score of the second child is <code>DBL_MAX</code>).</li>
</ul>

<p>Also, we could implement a pure <code>DefeatistTreeTraverser</code>, for every kind of tree (not only spill trees) that always considers the score of all the child nodes, chose the one with the lowest score and doesn't do backtracking.</p>

<p>Thanks!</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-238137161">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFHQgingNfJEZhi7gmO33uiDlP-BGks5qdqmggaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFNmgu5R0bOnFTnfinvn8Balia6aAks5qdqmggaJpZM4JZzLU.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-238137161"></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":"@MarcosPividori in #747: @rcurtin  Thanks for your feedback! \r\n\r\nI implemented Hybrid Spill Search. It does:\r\n + backtracking in non-overlapping node.\r\n + defeatist search on overlapping nodes.\r\n\r\nSo, it is different to pure defeatist search.\r\n\r\nBecause of that, I think we should continue using the Tree Traversers for the implementation.\r\n\r\nI agree that code could be improved to avoid calculating the score of both child nodes (which means calculating the projection 2 times). It can make a difference, especially with non axis-orthogonal splitting hyperplanes, because the projection takes O(d) time.\r\n\r\nSo, I can implement a new method as you suggested:  \"GetNearestChild()\" and use it when working with a overlapping node in the `SingleTreeTraverser` and `DualTreeTraverser`.\r\n\r\nThat method is not strictly necessary. We could avoid including a new method, implementing it in a simply way:\r\nIf I have a overlapping node I calculate the score of one child, and decide based on that score without calculating the score of the second child:\r\n- If the score of the first child is `DBL_MAX`, I have to traverse the second child (its score is `0`).\r\n- If the score of the first child is `0`, I have to traverse the first child (the score of the second child is `DBL_MAX`).\r\n\r\nAlso, we could implement a pure `DefeatistTreeTraverser`, for every kind of tree (not only spill trees) that always considers the score of all the child nodes, chose the one with the lowest score and doesn't do backtracking.\r\n\r\nThanks!"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747#issuecomment-238137161"}}}</script>