3.8. APPLICATIONS OF LOCALITY-SENSITIVE HASHING
121
would not be reﬂected in the representation of the Web page containing that
ad. On the other hand, the sentence from Example 3.24 would be represented
by ﬁve shingles: “I recommend that,” “that you buy,” “you buy Sudzo,” “for
your laundry,” and “your laundry x,” where x is whatever word follows that
sentence.
Suppose we have two Web pages, each of which consists of half news text
and half ads or other material that has a low density of stop words. If the news
text is the same but the surrounding material is diﬀerent, then we would expect
that a large fraction of the shingles of the two pages would be the same. They
might have a Jaccard similarity of 75%. However, if the surrounding material
is the same but the news content is diﬀerent, then the number of common
shingles would be small, perhaps 25%.
If we were to use the conventional
shingling, where shingles are (say) sequences of 10 consecutive characters, we
would expect the two documents to share half their shingles (i.e., a Jaccard
similarity of 1/3), regardless of whether it was the news or the surrounding
material that they shared.
3.8.7
Exercises for Section 3.8
Exercise 3.8.1: Suppose we are trying to perform entity resolution among
bibliographic references, and we score pairs of references based on the similar-
ities of their titles, list of authors, and place of publication. Suppose also that
all references include a year of publication, and this year is equally likely to be
any of the ten most recent years. Further, suppose that we discover that among
the pairs of references with a perfect score, there is an average diﬀerence in the
publication year of 0.1.7 Suppose that the pairs of references with a certain
score s are found to have an average diﬀerence in their publication dates of 2.
What is the fraction of pairs with score s that truly represent the same pub-
lication? Note: Do not make the mistake of assuming the average diﬀerence
in publication date between random pairs is 5 or 5.5. You need to calculate it
exactly, and you have enough information to do so.
Exercise 3.8.2: Suppose we use the family F of functions described in Sec-
tion 3.8.5, where there is a 20% chance of a minutia in an grid square, an 80%
chance of a second copy of a ﬁngerprint having a minutia in a grid square where
the ﬁrst copy does, and each function in F being formed from three grid squares.
In Example 3.23, we constructed family F1 by using the OR construction on
1024 members of F. Suppose we instead used family F2 that is a 2048-way OR
of members of F.
(a) Compute the rates of false positives and false negatives for F2.
(b) How do these rates compare with what we get if we organize the same
2048 functions into a 2-way AND of members of F1, as was discussed at
the end of Section 3.8.5?
7We might expect the average to be 0, but in practice, errors in publication year do occur.
