118
CHAPTER 3. FINDING SIMILAR ITEMS
that grid squares from two images have a signiﬁcantly higher probability of
agreeing in the presence or absence of a minutia than if they were from images
of diﬀerent ﬁngers.
Thus, ﬁngerprints can be represented by sets of grid squares – those where
their minutiae are located – and compared like any sets, using the Jaccard sim-
ilarity or distance. There are two versions of ﬁngerprint comparison, however.
• The many-one problem is the one we typically expect. A ﬁngerprint has
been found on a gun, and we want to compare it with all the ﬁngerprints
in a large database, to see which one matches.
• The many-many version of the problem is to take the entire database, and
see if there are any pairs that represent the same individual.
While the many-many version matches the model that we have been following
for ﬁnding similar items, the same technology can be used to speed up the
many-one problem.
3.8.5
A LSH Family for Fingerprint Matching
We could minhash the sets that represent a ﬁngerprint, and use the standard
LSH technique from Section 3.4. However, since the sets are chosen from a
relatively small set of grid points (perhaps 1000), the need to minhash them
into more succinct signatures is not clear. We shall study here another form of
locality-sensitive hashing that works well for data of the type we are discussing.
Suppose for an example that the probability of ﬁnding a minutia in a random
grid square of a random ﬁngerprint is 20%. Also, assume that if two ﬁngerprints
come from the same ﬁnger, and one has a minutia in a given grid square, then
the probability that the other does too is 80%. We can deﬁne a locality-sensitive
family of hash functions as follows. Each function f in this family F is deﬁned
by three grid squares. Function f says “yes” for two ﬁngerprints if both have
minutiae in all three grid squares, and otherwise f says “no.” Put another
way, we may imagine that f sends to a single bucket all ﬁngerprints that have
minutiae in all three of f’s grid points, and sends each other ﬁngerprint to a
bucket of its own. In what follows, we shall refer to the ﬁrst of these buckets as
“the” bucket for f and ignore the buckets that are required to be singletons.
If we want to solve the many-one problem, we can use many functions from
the family F and precompute their buckets of ﬁngerprints to which they answer
“yes.” Then, given a new ﬁngerprint that we want to match, we determine
which of these buckets it belongs to and compare it with all the ﬁngerprints
found in any of those buckets. To solve the many-many problem, we compute
the buckets for each of the functions and compare all ﬁngerprints in each of the
buckets.
Let us consider how many functions we need to get a reasonable probability
of catching a match, without having to compare the ﬁngerprint on the gun with
each of the millions of ﬁngerprints in the database. First, the probability that
