<p>Hi <a href="https://github.com/rcurtin" class="user-mention">@rcurtin</a>,</p>

<p>Thanks for your comments.</p>

<p>We can do <em>"pure defeatist search"</em> with <code>SpillTrees</code>, without implementing a new tree traversal <code>DefeatistTreeTraversel</code>.</p>

<p>If we set: <code>rho = 0.99999</code>, all nodes will be <em>overlapping nodes</em>, and the spill tree's traversers will do defeatist search when visiting each of them.</p>

<p>The problem with that approach, which <em>hybrid spill tree</em> aims to solve, is that the tree can be really big. We can't be sure that the tree is reduced by a constant factor.</p>

<p>The default value for <em>rho</em> is: <code>0.7</code>. If we consider higher values, we will spend more time building the tree, but less time searching for the neighbors. The opposite for lower values of <em>rho</em>.</p>

<p>So, I think it only make sense to create a new <code>DefeatistTreeTraverser</code> if we want to do defeatist search with other tree types, different to <code>SpillTrees</code>. Would you agree?</p>

<p>In that case I don't think we need to implement a new method: <code>GetNearestChild()</code> for each Tree Type. We could continue considering the <code>Score()</code> method, evaluating each child and choosing the one with lowest score. (We could modify the <code>DefeatistTreeTraverser</code> class for <code>SpillTrees</code> to avoid calculating the projections of both nodes, calculate the score of one child, and decide based on that score without calculating the score of the second child, as I mentioned before).<br>
The only problem is that Score() would include the unnecessary overhead of CalculateBounds() which will be ignored by <em>pure defeatist search</em>. We should think how to avoid that.</p>

<p>What do you think? If you agree I can work on this once we finish with this PR.</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-239206014">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFG27VLK-1ONFYMrK2Yf--09lQMFZks5qe0a1gaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFPLUbXdlQqVwvQ6toeQ-gVaMwE7Dks5qe0a1gaJpZM4JZzLU.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-239206014"></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":"@MarcosPividori in #747: Hi @rcurtin,\r\n\r\nThanks for your comments.\r\n\r\nWe can do *\"pure defeatist search\"* with `SpillTrees`, without implementing a new tree traversal `DefeatistTreeTraversel`.\r\n\r\nIf we set: `rho = 0.99999`, all nodes will be *overlapping nodes*, and the spill tree's traversers will do defeatist search when visiting each of them.\r\n\r\nThe problem with that approach, which *hybrid spill tree* aims to solve, is that the tree can be really big. We can't be sure that the tree is reduced by a constant factor.\r\n\r\nThe default value for *rho* is: `0.7`. If we consider higher values, we will spend more time building the tree, but less time searching for the neighbors. The opposite for lower values of *rho*.\r\n\r\nSo, I think it only make sense to create a new `DefeatistTreeTraverser` if we want to do defeatist search with other tree types, different to `SpillTrees`. Would you agree?\r\n\r\nIn that case I don't think we need to implement a new method: `GetNearestChild()` for each Tree Type. We could continue considering the `Score()` method, evaluating each child and choosing the one with lowest score. (We could modify the `DefeatistTreeTraverser` class for `SpillTrees` to avoid calculating the projections of both nodes, calculate the score of one child, and decide based on that score without calculating the score of the second child, as I mentioned before).\r\nThe only problem is that Score() would include the unnecessary overhead of CalculateBounds() which will be ignored by *pure defeatist search*. We should think how to avoid that.\r\n\r\nWhat do you think? If you agree I can work on this once we finish with this PR.\r\n\r\nThanks!\r\n"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747#issuecomment-239206014"}}}</script>