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

[Ryan Curtin]

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

Yes, so the issue here is that we can have situations where we end up with no candidates at all (or fewer than k candidates) for a particular query point, because we would be pruning based on a too-tight B_2.  I think it is still possible to prune in this case, but there is a little extra trickery involved in order to handle that.  Basically if we were pruning based on a too-tight B_2, we would need to go through the tree and, for any query nodes with descendant points that are missing neighbors, we could use the reference points that B_2 was calculated with as those missing neighbors.  I haven't worked the math and am not in a position to do so at the moment, but I think it's right.

Implementing that would be somewhat complex, so, I am not sure if that's worth doing now.

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