<p>In <a href="https://github.com/mlpack/mlpack/pull/747#discussion_r74707921">src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp</a>:</p>
<pre style='color:#555'>> @@ -375,6 +375,9 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Rescore(
> if (oldScore == DBL_MAX)
> return oldScore;
>
> + if (oldScore == SortPolicy::BestDistance())
> + return oldScore;
</pre>
<p><code>SortPolicy::BestDistance()</code> is <code>DBL_MAX</code>, if <code>SortPolicy = FurthestNeighborSort</code>, so this statement would end up being meaningless. I think that what you are meaning to do here is avoid calculating the bound if there is no possibility of pruning, but in that case the score should be <code>0.0</code>, so we should probably instead write this:</p>
<pre><code>if (oldScore == DBL_MAX || oldScore == 0.0)
return oldScore;
</code></pre>
<p>Two small notes:</p>
<ol>
<li><p>I realized, while writing this comment, that the furthest neighbor search actually did not invert the distances before they were returned! This means that the runtime of furthest neighbor search was far slower than it needed to be, since the traversal would always recurse into the worst node combination first! I added some methods to <code>SortPolicy</code> to convert distances to and from scores in <a href="https://github.com/mlpack/mlpack/commit/1092b1cbbb35ea83be5679d8a2fa80464a859339" class="commit-link"><tt>1092b1c</tt></a>, so now furthest-neighbor-search is much faster.</p></li>
<li><p>Technically I think it is possible to prune if the score is 0, so this short-circuit may sometimes overlook those situations: for instance, if you have a nearest neighbor with distance 0, you don't need to look at any other nearest neighbors that could have a distance of 0---you already have a candidate with that distance. But for our implementation here, bounds like B_2() mean that we cannot prune in those situations. So my little footnote here is inapplicable to our situation, but I still wanted to point it out. :)</p></li>
</ol>
<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/files/fe090ee13c7cad79e2b7eb8b6690628ba3ead1ed#r74707921">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFG0VyfrVHhxPhiAPvAntpNcRhC1eks5qf3rxgaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFGyCl96zQgb1rLWchZHBvan3RdBcks5qf3rxgaJpZM4JZzLU.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/files/fe090ee13c7cad79e2b7eb8b6690628ba3ead1ed#r74707921"></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 #747: `SortPolicy::BestDistance()` is `DBL_MAX`, if `SortPolicy = FurthestNeighborSort`, so this statement would end up being meaningless. I think that what you are meaning to do here is avoid calculating the bound if there is no possibility of pruning, but in that case the score should be `0.0`, so we should probably instead write this:\r\n\r\n```\r\nif (oldScore == DBL_MAX || oldScore == 0.0)\r\n return oldScore;\r\n```\r\n\r\nTwo small notes:\r\n\r\n1. I realized, while writing this comment, that the furthest neighbor search actually did not invert the distances before they were returned! This means that the runtime of furthest neighbor search was far slower than it needed to be, since the traversal would always recurse into the worst node combination first! I added some methods to `SortPolicy` to convert distances to and from scores in 1092b1c, so now furthest-neighbor-search is much faster.\r\n\r\n2. Technically I think it is possible to prune if the score is 0, so this short-circuit may sometimes overlook those situations: for instance, if you have a nearest neighbor with distance 0, you don't need to look at any other nearest neighbors that could have a distance of 0---you already have a candidate with that distance. But for our implementation here, bounds like B_2() mean that we cannot prune in those situations. So my little footnote here is inapplicable to our situation, but I still wanted to point it out. :)"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747/files/fe090ee13c7cad79e2b7eb8b6690628ba3ead1ed#r74707921"}}}</script>