116
CHAPTER 3. FINDING SIMILAR ITEMS
son, 100 points was assigned to each of the three ﬁelds, so records with exact
matches in all three ﬁelds got a score of 300. However, there were deductions for
mismatches in each of the three ﬁelds. As a ﬁrst approximation, edit-distance
(Section 3.5.5) was used, but the penalty grew quadratically with the distance.
Then, certain publicly available tables were used to reduce the penalty in ap-
propriate situations. For example, “Bill” and “William” were treated as if they
diﬀered in only one letter, even though their edit-distance is 5.
However, it is not feasible to score all one trillion pairs of records. Thus,
a simple LSH was used to focus on likely candidates. Three “hash functions”
were used. The ﬁrst sent records to the same bucket only if they had identical
names; the second did the same but for identical addresses, and the third did
the same for phone numbers. In practice, there was no hashing; rather the
records were sorted by name, so records with identical names would appear
consecutively and get scored for overall similarity of the name, address, and
phone.
Then the records were sorted by address, and those with the same
address were scored. Finally, the records were sorted a third time by phone,
and records with identical phones were scored.
This approach missed a record pair that truly represented the same person
but none of the three ﬁelds matched exactly. Since the goal was to prove in
a court of law that the persons were the same, it is unlikely that such a pair
would have been accepted by a judge as suﬃciently similar anyway.
3.8.3
Validating Record Matches
What remains is to determine how high a score indicates that two records truly
represent the same individual.
In the example at hand, there was an easy
way to make that decision, and the technique can be applied in many similar
situations. It was decided to look at the creation-dates for the records at hand,
and to assume that 90 days was an absolute maximum delay between the time
the service was bought at Company A and registered at B. Thus, a proposed
match between two records that were chosen at random, subject only to the
constraint that the date on the B-record was between 0 and 90 days after the
date on the A-record, would have an average delay of 45 days.
It was found that of the pairs with a perfect 300 score, the average delay was
10 days. If you assume that 300-score pairs are surely correct matches, then you
can look at the pool of pairs with any given score s, and compute the average
delay of those pairs. Suppose that the average delay is x, and the fraction of
true matches among those pairs with score s is f. Then x = 10f + 45(1 −f),
or x = 45 −35f. Solving for f, we ﬁnd that the fraction of the pairs with score
s that are truly matches is (45 −x)/35.
The same trick can be used whenever:
1. There is a scoring system used to evaluate the likelihood that two records
represent the same entity, and
