3.8. APPLICATIONS OF LOCALITY-SENSITIVE HASHING
117
When Are Record Matches Good Enough?
While every case will be diﬀerent, it may be of interest to know how the
experiment of Section 3.8.3 turned out on the data of Section 3.8.2. For
scores down to 185, the value of x was very close to 10; i.e., these scores
indicated that the likelihood of the records representing the same person
was essentially 1. Note that a score of 185 in this example represents a
situation where one ﬁeld is the same (as would have to be the case, or the
records would never even be scored), one ﬁeld was completely diﬀerent,
and the third ﬁeld had a small discrepancy. Moreover, for scores as low as
115, the value of x was noticeably less than 45, meaning that some of these
pairs did represent the same person. Note that a score of 115 represents
a case where one ﬁeld is the same, but there is only a slight similarity in
the other two ﬁelds.
2. There is some ﬁeld, not used in the scoring, from which we can derive a
measure that diﬀers, on average, for true pairs and false pairs.
For instance, suppose there were a “height” ﬁeld recorded by both companies
A and B in our running example. We can compute the average diﬀerence in
height for pairs of random records, and we can compute the average diﬀerence in
height for records that have a perfect score (and thus surely represent the same
entities). For a given score s, we can evaluate the average height diﬀerence of the
pairs with that score and estimate the probability of the records representing
the same entity. That is, if h0 is the average height diﬀerence for the perfect
matches, h1 is the average height diﬀerence for random pairs, and h is the
average height diﬀerence for pairs of score s, then the fraction of good pairs
with score s is (h1 −h)/(h1 −h0).
3.8.4
Matching Fingerprints
When ﬁngerprints are matched by computer, the usual representation is not
an image, but a set of locations in which minutiae are located. A minutia,
in the context of ﬁngerprint descriptions, is a place where something unusual
happens, such as two ridges merging or a ridge ending. If we place a grid over a
ﬁngerprint, we can represent the ﬁngerprint by the set of grid squares in which
minutiae are located.
Ideally, before overlaying the grid, ﬁngerprints are normalized for size and
orientation, so that if we took two images of the same ﬁnger, we would ﬁnd
minutiae lying in exactly the same grid squares. We shall not consider here
the best ways to normalize images. Let us assume that some combination of
techniques, including choice of grid size and placing a minutia in several adjacent
grid squares if it lies close to the border of the squares enables us to assume
