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.