<p>In <a href="https://github.com/mlpack/mlpack/pull/684#discussion_r66668125">src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp</a>:</p>
<pre style='color:#555'>> @@ -150,6 +150,21 @@ class NearestNeighborSort
> return DBL_MAX;
> return a + b;
> }
> +
> + /**
> + * Return the given value relaxed.
> + *
> + * @param value Value to relax.
> + * @param epsilon Relative error (non-negative).
> + *
> + * @return double Value relaxed.
> + */
> + static inline double Relax(const double value, const double epsilon)
> + {
> + if (value == DBL_MAX)
> + return DBL_MAX;
> + return (1 / (1 + epsilon)) * value;
</pre>
<p><a href="https://github.com/rcurtin" class="user-mention">@rcurtin</a><br>
Thanks for your reply. I am no sure about this...</p>
<p>I think this could be confusing for future users, because we would be adopting different approaches for KNN and KFN.</p>
<p>For KNN we consider the relative error of the <em>approximated value</em> against the <em>true value</em>. So, we assert that:</p>
<pre><code>| d(p_q, p_r) - d(p_q, p_r^*) | / | d(p_q, p_r^*) | <= e
</code></pre>
<p>So, I suggest to take exactly the same approach for KFN. We make an assertion about the relative error of our <em>approximation</em> against the <em>true value</em>:</p>
<pre><code>| d(p_q, p_r) - d(p_q, p_r^*) | / | d(p_q, p_r^*) | <= e
</code></pre>
<p>However, you propose to consider a different approach for KFN:</p>
<pre><code>| d(p_q, p_r) - d(p_q, p_r^*) | / | d(p_q, p_r) | <= e
</code></pre>
<p>This calculates the proportion in relation to the <em>approximation value</em>, instead of the <em>true value</em>.<br>
Instead of asserting:</p>
<pre><code>| d(p_q, p_r) - d(p_q, p_r^*) | <= e * | d(p_q, p_r^*) |
</code></pre>
<p>You are asserting that:</p>
<pre><code>| d(p_q, p_r) - d(p_q, p_r^*) | <= e * | d(p_q, p_r) |
</code></pre>
<p>So, these are different approches.<br>
I have been looking for documentation of furthest neighbor search. Both approaches are considered:</p>
<p>Using relative error as I propose:</p>
<ul>
<li><p>Farthest neighbors, maximum spanning trees and related problems in higher dimensions. <a href="http://www.sciencedirect.com/science/article/pii/0925772192900019">[ref]</a></p></li>
<li><p>Approximate Weighted Farthest Neighbors and Minimum Dilation Stars. <a href="https://arxiv.org/pdf/cs/0602029.pdf">[ref]</a></p></li>
</ul>
<p>Considering approximation as you proposes:</p>
<ul>
<li><p>Reductions Among High Dimensional Proximity Problems. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.6492&rep=rep1&type=pdf">[ref]</a><br>
Defines the c-Furthest Neighbor Search Problem (c-FNS).</p></li>
<li><p>Approximate Furthest Neighbor in High Dimensions. <a href="http://www.itu.dk/people/jovt/main.pdf">[ref]</a><br>
Defines c-approximate furthest neighbor (c-AFN).</p></li>
</ul>
<p>Personally, I would prefer the first approach, because it mentions the relative error of the <em>approximation</em> against the <em>true value</em>. This is similar to the definition of relative error: <a href="https://en.wikipedia.org/wiki/Approximation_error#Formal_Definition">[ref]</a><br>
Also, it is the same as for KNN...</p>
<p>Of course, if you prefer I can change it.</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/684/files/07879a2cc79b35b10d7fae687d6e27ad90a9f2d7#r66668125">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFMzGVlstRMDuy0PTS3qZ-K999-YZks5qKboOgaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFHpatF-VdEzkNiakvOL3McD1bWIHks5qKboOgaJpZM4IvhJu.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/684/files/07879a2cc79b35b10d7fae687d6e27ad90a9f2d7#r66668125"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>