<p>In <a href="https://github.com/mlpack/mlpack/pull/684#discussion_r66622904">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>This method is meant to be used to relax the <strong>bound value</strong>.<br>
If you have a bound value B of the worst distance. To do approximation, I will change it to :</p>
<ul>
<li>(1 / (1 + epsilon)) * B in KNN.</li>
<li>(1 / (1 - epsilon)) * B in KFN.
(similar to what was mentioned in your paper)</li>
</ul>
<p>For example, for e=0.5-approximate furthest neighbor: (admiting a relative error of the 50%)<br>
Instead of the rule: if d_{max}(N_q,N_r) < B prune<br>
We will consider: if d_{max}(N_q,N_r) < 2 * B prune<br>
Which is the same that: if 0.5 * d_{max}(N_q,N_r) < B prune<br>
This means: if our worst distance B is within the 50% relative error of d_{max}(N_q,N_r), we can prune, because our current results are acceptable.</p>
<p>For KNN having an e >=1 value makes sense because:<br>
If <em>best</em> is the nearest neighbor distance, we want our resultant distance <em>res</em> to satisfy: (1-e) * best <= res <= (1+e) * best<br>
As best <= res. It is simplified to satisfy: res <= (1+e) * best<br>
So, if e >=1, for example e=2, we are looking for solutions that satisfy: res <= 3 * best</p>
<p>On the other hand, for KFN having an e >=1 value doesn't makes sense because:<br>
If <em>best</em> is the furthest neighbor distance, we want our resultant distance <em>res</em> to satisfy: (1-e) * best <= res <= (1+e) * best<br>
As best >= res. It is simplified to satisfy: (1-e) * best <= res<br>
So, if e >=1, for example e=1, we are looking for solutions that satisfy: 0 <= res , it implies, we are accepting any result.</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#r66622904">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFJTai_-DrRIRMasYuwHJ97vUDhNnks5qKXVjgaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFHFJeunCLqMb3uQq0WwawstNSMcYks5qKXVjgaJpZM4IvhJu.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#r66622904"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>