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.