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

MarcosPividori notifications at github.com
Fri Jun 10 11:11:47 EDT 2016


> @@ -419,6 +423,8 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::
>    queryNode.Stat().SecondBound() = bestDistance;
>    queryNode.Stat().AuxBound() = auxDistance;
>  
> +  worstDistance = SortPolicy::Relax(worstDistance, epsilon);

We can only relax the B_1 bound (worst distance).  We can not change the B_2 bound (best distance).
I will try to make this clear, let me know it this isn't:
For B_1, we are considering the worst distance. 
For B_2, in KNN we are estimating an upper bound of the best distance for all descendants of a node N_q, based on the distance calculated for some descendants.
For example in KNN, suppose that our estimation is based on the distance calculated from a descendant point *p_q* in DescendantsPoints(N_q) and the reference point p_r. I mean, B_2 bound was calculated doing triangulation, using: dist(p_q,p_r):
  So B_2(N_q) = dist(p_q,p_r) + some triangulation...
In exact KNN we don't have any problem when prunning if d_{min}(N_q,N_r) > B_2(N_q) . We can be sure that for all p_s in Descendants(N_q), the combination (p_s , p_r) will be considered at some moment, because we know dist(p_s , p_r) <= B_2(N_q).

On the other hand, when doing approximation, we can not relax the value to: 0.5  * B_2(N_q).
For some p_s in Descendants(N_q), the combination (p_s , p_r) could be pruned before being considered. We can not assert that:  dist(p_s , p_r) <= 0.5 * B_2(N_q).

If this is not clear, I could provide an example tree where approximation would fail.

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


More information about the mlpack-git mailing list