3.8. APPLICATIONS OF LOCALITY-SENSITIVE HASHING
119
two ﬁngerprints from diﬀerent ﬁngers would be in the bucket for a function f
in F is (0.2)6 = 0.000064. The reason is that they will both go into the bucket
only if they each have a minutia in each of the three grid points associated with
f, and the probability of each of those six independent events is 0.2.
Now, consider the probability that two ﬁngerprints from the same ﬁnger
wind up in the bucket for f.
The probability that the ﬁrst ﬁngerprint has
minutiae in each of the three squares belonging to f is (0.2)3 = 0.008. However,
if it does, then the probability is (0.8)3 = 0.512 that the other ﬁngerprint
will as well.
Thus, if the ﬁngerprints are from the same ﬁnger, there is a
0.008 × 0.512 = 0.004096 probability that they will both be in the bucket of f.
That is not much; it is about one in 200. However, if we use many functions
from F, but not too many, then we can get a good probability of matching
ﬁngerprints from the same ﬁnger while not having too many false positives –
ﬁngerprints that must be considered but do not match.
Example 3.23 :
For a speciﬁc example, let us suppose that we use 1024
functions chosen randomly from F.
Next, we shall construct a new fam-
ily F1 by performing a 1024-way OR on F.
Then the probability that F1
will put ﬁngerprints from the same ﬁnger together in at least one bucket is
1 −(1 −0.004096)1024 = 0.985.
On the other hand, the probability that
two ﬁngerprints from diﬀerent ﬁngers will be placed in the same bucket is
(1 −(1 −0.000064)1024 = 0.063. That is, we get about 1.5% false negatives
and about 6.3% false positives.
✷
The result of Example 3.23 is not the best we can do. While it oﬀers only a
1.5% chance that we shall fail to identify the ﬁngerprint on the gun, it does force
us to look at 6.3% of the entire database. Increasing the number of functions
from F will increase the number of false positives, with only a small beneﬁt
of reducing the number of false negatives below 1.5%. On the other hand, we
can also use the AND construction, and in so doing, we can greatly reduce
the probability of a false positive, while making only a small increase in the
false-negative rate. For instance, we could take 2048 functions from F in two
groups of 1024. Construct the buckets for each of the functions. However, given
a ﬁngerprint P on the gun:
1. Find the buckets from the ﬁrst group in which P belongs, and take the
union of these buckets.
2. Do the same for the second group.
3. Take the intersection of the two unions.
4. Compare P only with those ﬁngerprints in the intersection.
Note that we still have to take unions and intersections of large sets of ﬁnger-
prints, but we compare only a small fraction of those. It is the comparison of
