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

MarcosPividori notifications at github.com
Fri Jun 10 15:25:02 EDT 2016


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

@rcurtin
Thanks for your reply. I am no sure about this...

I think this could be confusing for future users, because we would be adopting different approaches for KNN and KFN.

For KNN we consider the relative error of the *approximated value* against the *true value*. So, we assert that:
```
|  d(p_q, p_r)   -   d(p_q, p_r^*) |     /     |  d(p_q, p_r^*) |     <=   e
```
So, I suggest to take exactly the same approach for KFN. We make an assertion about the relative error of our *approximation* against the *true value*:
```
|  d(p_q, p_r)   -   d(p_q, p_r^*) |     /     |  d(p_q, p_r^*) |     <=   e
```

However, you propose to consider a different approach for KFN:
```
|  d(p_q, p_r)  - d(p_q, p_r^*) |     /     |  d(p_q, p_r) |     <=   e
```
This calculates the proportion in relation to the *approximation value*, instead of the *true value*.
Instead of asserting:
```
|  d(p_q, p_r)  - d(p_q, p_r^*) |    <=    e  *  |  d(p_q, p_r^*) |
```
You are asserting that:
```
|  d(p_q, p_r)  - d(p_q, p_r^*) |    <=    e  *  |  d(p_q, p_r) |
```

So, these are different approches.
I have been looking for documentation of furthest neighbor search. Both approaches are considered:

Using relative error as I propose:

+ Farthest neighbors, maximum spanning trees and related problems in higher dimensions. [[ref]](http://www.sciencedirect.com/science/article/pii/0925772192900019)

+ Approximate Weighted Farthest Neighbors and Minimum Dilation Stars. [[ref]](https://arxiv.org/pdf/cs/0602029.pdf)

Considering approximation as you proposes:

+ Reductions Among High Dimensional Proximity Problems. [[ref]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.6492&rep=rep1&type=pdf)
 Defines the c-Furthest Neighbor Search Problem (c-FNS).

+ Approximate Furthest Neighbor in High Dimensions. [[ref]](http://www.itu.dk/people/jovt/main.pdf)
 Defines c-approximate furthest neighbor (c-AFN).

Personally, I would prefer the first approach, because it mentions the relative error of the *approximation* against the *true value*. This is similar to the definition of relative error: [[ref]](https://en.wikipedia.org/wiki/Approximation_error#Formal_Definition)
Also, it is the same as for KNN...

Of course, if you prefer I can change it.

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


More information about the mlpack-git mailing list