[mlpack-git] [mlpack/mlpack] Implementation of Multiprobe LSH (#691)

[Yannis Mentekidis]

> I think that the offsets have a maximum, right? So every point from, e.g., the lower left cluster will fall not in the lower-leftmost bin, but instead in (I think) the 4 (or 9?) bins closest to the center of the lower-leftmost bin. (Or something like that.) If that's the case, we could then put the query point outside of the furthest possible bin, and then set a higher number of probes to ensure that at least one of the 4 (or 9) bins are checked.

You're right, the offsets have a maximum and better yet they're actually positive - so the translation they cause can only be to the right and upwards, and because of their maximum size (equal to hash width) they can move points up to one "block".


For the figure, let's take the C2 cluster centered at (3.5, 3.5).
That means we could simply replace the red point with one (say q1) directly under C2, as well as one inside C2's block (say q2). We can access the offsets from the LSHSearch object so we can actually place these wherever they "should be" to get hashed properly.
That way:

 * q1 should find no neighbors without multiprobe, and the neighbors that weren't translated away (so, hashed to C2's original block around) with 1 probe.
* q2 should find some neighbors inside C2 and should find all neighbors with 3 additional probes.

I'll start writing this and see how it goes.



---
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/691#issuecomment-229015517
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160628/4192ebc3/attachment.html>