So what locality sensitive hashing does, and this is the main trick in this
technique, is that you use many such functions f.
Remember, each function f corresponds to three chosen grid cells.
Now there are many, many choices for three cells.
Lets take a thousand such choices. And in general be such choices, now we
need to figure out what's the chance that. At least one function, out of these be a
thousand. Actually matches.
Let's work that out. First of all, pq^k, as we have just
computed, is the probability that f(x) = f(y) and their both one for a particular
combination of k cells. One minus of that, is the chance that f(x)
and f(y) are not one for these, k cells. So if you raise this to the power of b,
you'll get the chance that none of the b choices of f have a match.
That is f(x) and f(y) are not one for any of these b functions.
And then again, one minus of that is the chance that at least one of the b
functions matches. So let's go over that one more time.
We have the probability that. K cells match, which is pq^k.
One minus that is the probability that k cells don't match, then one - pq^k raise
to the b is the probability that none of the b functions has a match for x and y.
And then, another one minus that is the chance that at least one of these b
functions is such that f(x) and f(y) are both one.
And interestingly this nice functional form, gives me, gives us 0.997 for the
values p = 0.2, k = three and q = 0.9. And that means that by using many
functions, we get a very high chance that at least one of them will give us a match
if the two prints are actually from the same person.
And this is the trick Of locality sensitive hashing.