3.8. APPLICATIONS OF LOCALITY-SENSITIVE HASHING
115
3. Matching Newspaper Articles: Here, we consider a diﬀerent notion of
shingling that focuses attention on the core article in an on-line news-
paper’s Web page, ignoring all the extraneous material such as ads and
newspaper-speciﬁc material.
3.8.1
Entity Resolution
It is common to have several data sets available, and to know that they refer to
some of the same entities. For example, several diﬀerent bibliographic sources
provide information about many of the same books or papers. In the general
case, we have records describing entities of some type, such as people or books.
The records may all have the same format, or they may have diﬀerent formats,
with diﬀerent kinds of information.
There are many reasons why information about an entity may vary, even if
the ﬁeld in question is supposed to be the same. For example, names may be
expressed diﬀerently in diﬀerent records because of misspellings, absence of a
middle initial, use of a nickname, and many other reasons. For example, “Bob
S. Jomes” and “Robert Jones Jr.” may or may not be the same person. If
records come from diﬀerent sources, the ﬁelds may diﬀer as well. One source’s
records may have an “age” ﬁeld, while another does not. The second source
might have a “date of birth” ﬁeld, or it may have no information at all about
when a person was born.
3.8.2
An Entity-Resolution Example
We shall examine a real example of how LSH was used to deal with an entity-
resolution problem. Company A was engaged by Company B to solicit cus-
tomers for B. Company B would pay A a yearly fee, as long as the customer
maintained their subscription. They later quarreled and disagreed over how
many customers A had provided to B. Each had about 1,000,000 records, some
of which described the same people; those were the customers A had provided
to B. The records had diﬀerent data ﬁelds, but unfortunately none of those
ﬁelds was “this is a customer that A had provided to B.” Thus, the problem
was to match records from the two sets to see if a pair represented the same
person.
Each record had ﬁelds for the name, address, and phone number of the
person. However, the values in these ﬁelds could diﬀer for many reasons. Not
only were there the misspellings and other naming diﬀerences mentioned in
Section 3.8.1, but there were other opportunities to disagree as well. A customer
might give their home phone to A and their cell phone to B. Or they might
move, and tell B but not A (because they no longer had need for a relationship
with A). Area codes of phones sometimes change.
The strategy for identifying records involved scoring the diﬀerences in three
ﬁelds: name, address, and phone. To create a score describing the likelihood
that two records, one from A and the other from B, described the same per-
