<p>In <a href="https://github.com/mlpack/mlpack/pull/684#discussion_r66635114">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>I think there is some confusion here. I think you are referencing the paper "Faster dual-tree traversal for nearest neighbor search", where the relative-value approximate nearest neighbor search problem is defined as, for some given epsilon e, we must return a nearest neighbor such that <code>d(p_q, p_r) <= (1 + e) d(p_q, p_r^*)</code> where <code>p_r^*</code> is the true nearest neighbor (or, alternately written, that <code>(d(p_q, p_r^*) / d(p_q, p_r)) <= 1 / (1 + e)</code>).</p>
<p>But it is not reasonable to generalize to say that the relative value approximate furthest neighbor search problem is to return a furthest neighbor such that <code>d(p_q, p_r) >= (1 - e) d(p_q, p_r^*)</code> (where <code>p_r^*</code> is the true furthest neighbor), because this is not relative-value approximation. The user will expect that for a given e, then the furthest neighbor they are returned has distance within e% of the true furthest neighbor distance. This gives a different equation: <code>(1 + e) d(p_q, p_r) >= d(p_q, p_r^*)</code>. (Or, maybe easier to understand, <code>(d(p_q, p_r^*) / d(p_q, p_r)) <= (1 + e)</code>). This is how furthest neighbor search is defined in approximate furthest neighbor search papers (of which there are only a few---here is one: <a href="http://www.itu.dk/people/jovt/main.pdf">http://www.itu.dk/people/jovt/main.pdf</a> ).</p>
<p>From that starting point, this means that the bounds should be relaxed by a factor of <code>1 / (1 + epsilon)</code> for nearest neighbor search and the inverse of that, <code>(1 + epsilon)</code> for furthest neighbor search.</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#r66635114">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFFaxCOvMT37j4Bpwqyc7h7VvgPXzks5qKYWvgaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFKGGtaDZ3OGX12tiji6AkgP6UQ86ks5qKYWvgaJpZM4IvhJu.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#r66635114"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>