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

[MarcosPividori]

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

This method is meant to be used to relax the **bound value**.
If you have a bound value B of the worst distance. To do approximation, I will change it to :
 - (1 / (1 + epsilon))  * B   in KNN.
 - (1 / (1 - epsilon))  * B   in KFN.
 (similar to what was mentioned in your paper)

For example, for e=0.5-approximate furthest neighbor: (admiting a relative error of the 50%)
 Instead of the rule:    if    d_{max}(N_q,N_r) < B      prune
 We will consider:   if    d_{max}(N_q,N_r) <  2 * B      prune
 Which is the same that:    if  0.5 * d_{max}(N_q,N_r) <  B      prune
 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.


For KNN having an e >=1 value makes sense because:
   If   *best*   is the nearest neighbor distance, we want our resultant distance  *res* to satisfy:  (1-e) * best <= res <= (1+e) * best
  As best <= res.  It is simplified to satisfy: res <= (1+e) * best
  So, if e >=1, for example e=2, we are looking for solutions that satisfy:  res <= 3 * best

On the other hand, for KFN having an e >=1 value doesn't makes sense because:
   If   *best*   is the furthest neighbor distance, we want our resultant distance  *res* to satisfy:  (1-e) * best <= res <= (1+e) * best
  As best >= res.  It is simplified to satisfy: (1-e) * best <= res
  So, if e >=1, for example e=1, we are looking for solutions that satisfy:  0 <= res , it implies, we are accepting any result.

---
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#r66622904
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160610/b2651700/attachment.html>