<p><a href="https://github.com/rcurtin" class="user-mention">@rcurtin</a>, Thanks for your feedback!</p>
<p>In response to the comment: <a href="https://github.com/mlpack/mlpack/pull/747#issuecomment-239602549" class="issue-link js-issue-link" data-url="https://github.com/mlpack/mlpack/issues/747" data-id="168696245" data-error-text="Failed to load issue title" data-permission-text="Issue title is private">#747 (comment)</a><br>
A <code>defeatist single tree traverser</code> would perform a <code>greedy search</code> that chooses the child with the best score and doesn't do backtracking. We could also call it: <code>SingleTreeGreedyTraverser</code><br>
The problem of using <code>GetNearestChild()</code> inside the traverser instead of a <code>RuleType</code> template parameter, is that that traverser will only be useful for <em>neighbor search</em>.<br>
If we continue using the <code>Score()</code> function from the <code>RuleType</code> class, we can use it for other purposes such as: <em>Defeatist Farthest Neighbor search</em>, or any other algorithm that uses the single tree traverser and we want to provide a greedy alternative.</p>
<p>I think we could solve this problem this way:</p>
<ul>
<li>Add a new method to the <code>RuleType</code> class:</li>
</ul>
<pre><code>TreeType& GetChildWithBestScore(
const size_t queryIndex,
const TreeType& referenceNode);
</code></pre>
<ul>
<li>
<code>SingleTreeGreedyTraverser</code> will always call <code>GetChildWithBestScore()</code> and continue with that child until it reaches a leaf node.</li>
<li>We could implement <code>NeighborSearchRules::GetChildWithBestScore()</code> as :</li>
</ul>
<pre><code>TreeType& NeighborSearchRules::GetChildWithBestScore(
const size_t queryIndex,
const TreeType& referenceNode)
{
SortPolicy::GetBestChild(dataset.col(queryIndex), referenceNode);
}
</code></pre>
<pre><code>TreeType& NearestNeighborSort::GetBestChild(
const VecType& queryPoint,
const TreeType& referenceNode)
{
return referenceNode.GetNearestChild(queryPoint);
}
TreeType& FurthestNeighborSort::GetFurthestChild(
const VecType& queryPoint,
const TreeType& referenceNode)
{
return referenceNode.GetFurthestChild(queryPoint);
}
</code></pre>
<p>And the trivial implementation of that method for other RuleTypes would be:</p>
<pre><code>TreeType& SomeRuleType::GetChildWithBestScore(
const size_t queryPoint,
const TreeType& referenceNode)
{
size_t best_child = size_t() - 1;
size_t best_score = DBL_MAX;
for (size_t i = 0; i < referenceNode.NumChildren(); i++)
{
double score = Score(queryPoint, referenceNode.Child(i));
if (score < best_score)
{
best_score = score;
best_child = i;
}
}
return referenceNode.Child(best_child);
}
</code></pre>
<p>What do you think? This way we can take advantage of different tree types when it is possible to calculate which node a query point is closer to in less time. And, at the same time, we can use the <code>SingleTreeGreedyTraverser</code> for other purposes.</p>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<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-239870358">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFI1q3x8kTZ-CusYRFDogBn6ey2rEks5qgKOOgaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFAzCiRy1VIEYmM2SGtC067n0oalLks5qgKOOgaJpZM4JZzLU.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-239870358"></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: @rcurtin, Thanks for your feedback!\r\n\r\nIn response to the comment: https://github.com/mlpack/mlpack/pull/747#issuecomment-239602549\r\nA `defeatist single tree traverser` would perform a `greedy search` that chooses the child with the best score and doesn't do backtracking. We could also call it: `SingleTreeGreedyTraverser`\r\nThe problem of using `GetNearestChild()` inside the traverser instead of a `RuleType` template parameter, is that that traverser will only be useful for *neighbor search*.\r\nIf we continue using the `Score()` function from the `RuleType` class, we can use it for other purposes such as: *Defeatist Farthest Neighbor search*, or any other algorithm that uses the single tree traverser and we want to provide a greedy alternative.\r\n\r\nI think we could solve this problem this way:\r\n+ Add a new method to the `RuleType` class:\r\n```\r\nTreeType\u0026 GetChildWithBestScore(\r\n const size_t queryIndex,\r\n const TreeType\u0026 referenceNode);\r\n```\r\n+ `SingleTreeGreedyTraverser` will always call `GetChildWithBestScore()` and continue with that child until it reaches a leaf node.\r\n+ We could implement `NeighborSearchRules::GetChildWithBestScore()` as :\r\n```\r\nTreeType\u0026 NeighborSearchRules::GetChildWithBestScore(\r\n const size_t queryIndex,\r\n const TreeType\u0026 referenceNode)\r\n{\r\n SortPolicy::GetBestChild(dataset.col(queryIndex), referenceNode);\r\n}\r\n```\r\n```\r\nTreeType\u0026 NearestNeighborSort::GetBestChild(\r\n const VecType\u0026 queryPoint,\r\n const TreeType\u0026 referenceNode)\r\n{\r\n return referenceNode.GetNearestChild(queryPoint);\r\n}\r\n\r\nTreeType\u0026 FurthestNeighborSort::GetFurthestChild(\r\n const VecType\u0026 queryPoint,\r\n const TreeType\u0026 referenceNode)\r\n{\r\n return referenceNode.GetFurthestChild(queryPoint);\r\n}\r\n```\r\n\r\nAnd the trivial implementation of that method for other RuleTypes would be:\r\n```\r\nTreeType\u0026 SomeRuleType::GetChildWithBestScore(\r\n const size_t queryPoint,\r\n const TreeType\u0026 referenceNode)\r\n{\r\n size_t best_child = size_t() - 1;\r\n size_t best_score = DBL_MAX;\r\n for (size_t i = 0; i \u003c referenceNode.NumChildren(); i++)\r\n {\r\n double score = Score(queryPoint, referenceNode.Child(i));\r\n if (score \u003c best_score)\r\n {\r\n best_score = score;\r\n best_child = i;\r\n }\r\n }\r\n return referenceNode.Child(best_child);\r\n}\r\n```\r\n\r\nWhat do you think? This way we can take advantage of different tree types when it is possible to calculate which node a query point is closer to in less time. And, at the same time, we can use the `SingleTreeGreedyTraverser` for other purposes."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747#issuecomment-239870358"}}}</script>