[mlpack-git] [mlpack/mlpack] Approximate Neighbor Search for Dual tree algorithms. (#684)

[Ryan Curtin]

> @@ -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;

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 `d(p_q, p_r) <= (1 + e) d(p_q, p_r^*)` where `p_r^*` is the true nearest neighbor (or, alternately written, that `(d(p_q, p_r^*) / d(p_q, p_r)) <= 1 / (1 + e)`).

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 `d(p_q, p_r) >= (1 - e) d(p_q, p_r^*)` (where `p_r^*` 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: `(1 + e) d(p_q, p_r) >= d(p_q, p_r^*)`.  (Or, maybe easier to understand, `(d(p_q, p_r^*) / d(p_q, p_r)) <= (1 + e)`).  This is how furthest neighbor search is defined in approximate furthest neighbor search papers (of which there are only a few---here is one: http://www.itu.dk/people/jovt/main.pdf ).

>From that starting point, this means that the bounds should be relaxed by a factor of `1 / (1 + epsilon)` for nearest neighbor search and the inverse of that, `(1 + epsilon)` for furthest neighbor search.

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/684/files/07879a2cc79b35b10d7fae687d6e27ad90a9f2d7#r66635114
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160610/e10133a4/attachment-0001.html>