To go into some detail, let's take a look at how one might do locality sensitive
hashing for fingerprint matching. This example is covered in
Rajaraman/Ullman so you can read about it there as well.
Fingerprints match if their minutiae match.
Now, minutiae is a technical term in the world of fingerprints, which I don't claim
to understand in great detail. But things like islands, ridges,
bifurcations, cores, crossovers, these are the terms used in that field.
We won't get into the details to the different types of minutiae, instead we
will only worry about whether a particular print has some minutiae in a particular
grid point, So we assume grid of cells to be placed on the fingerprint and.
We only measuring whether or not. A cell contains, a minutia.
Of some kind. Now, we define a function f(x) for a
print'x', which is one if the print has minutia in a specified set of'k' mid
positions. So function'f' depends on these
particular'k' positions. We'll use'k' is equal to three in the
example going forward. Notice that the function f is dependent on
the choice of the k-grid positions. If you choose a different set of grid
positions, you'll get a different function f.
Now let's consider the probability that any print.
Has a probab, has a menu shay, in a particular position, let that be P.
Not every print has menu shay in every position, but across all possible prints.
A particular position has menu shay with probability P.
Lets assume that the distribution is uniform and the probability is P.
Not necessarily a great assumption but for our example, it will suffice.
Now, the probability that f of x is equal to one, that is that the print x has
minutiae in all k positions. Is p raised to the power of k.
So if you take the probability that a particular cell has, menu shay is 0.2, the
probability of that, a set of three chosen cells, all have menu shay, is obviously
0.2 raise to the power three which is 0.008.
Now let's consider another print, y, but from the same person.
Its quiet likely that this print will have when you say in the same position as X,
but its not always the case. So lets assign a probability Q, it will be
quiet high that the print Y will have when you say, if X also does, in a particular
grid cell. Now let's look at the function F.
What is the probability that F of X is one and F of Y is also one?
Well, first of all the probability that F of X is one is P to the K, so that needs
to happen. But then.
You have the probability that. Y also has to have menu shay in the same K
position, so you multiply it by Q, K times, so you get P Q to the K.
Q is 0.9 that means there is 90 percent chance that Y will have menu shay if X
also does in a particular cell, then P Q to the three, works out 2.006.
Well, that's not so nice that both x and y get a yes match with the function f is
only. Happening with the probability.006.