120
CHAPTER 3. FINDING SIMILAR ITEMS
ﬁngerprints that takes the bulk of the time; in steps (1) and (2) ﬁngerprints
can be represented by their integer indices in the database.
If we use this scheme, the probability of detecting a matching ﬁngerprint
is (0.985)2 = 0.970; that is, we get about 3% false negatives. However, the
probability of a false positive is (0.063)2 = 0.00397. That is, we only have to
examine about 1/250th of the database.
3.8.6
Similar News Articles
Our last case study concerns the problem of organizing a large repository of
on-line news articles by grouping together Web pages that were derived from
the same basic text. It is common for organizations like The Associated Press
to produce a news item and distribute it to many newspapers. Each newspaper
puts the story in its on-line edition, but surrounds it by information that is
special to that newspaper, such as the name and address of the newspaper,
links to related articles, and links to ads. In addition, it is common for the
newspaper to modify the article, perhaps by leaving oﬀthe last few paragraphs
or even deleting text from the middle. As a result, the same news article can
appear quite diﬀerent at the Web sites of diﬀerent newspapers.
The problem looks very much like the one that was suggested in Section 3.4:
ﬁnd documents whose shingles have a high Jaccard similarity. Note that this
problem is diﬀerent from the problem of ﬁnding news articles that tell about the
same events. The latter problem requires other techniques, typically examining
the set of important words in the documents (a concept we discussed brieﬂy
in Section 1.3.1) and clustering them to group together diﬀerent articles about
the same topic.
However, an interesting variation on the theme of shingling was found to be
more eﬀective for data of the type described. The problem is that shingling as
we described it in Section 3.2 treats all parts of a document equally. However,
we wish to ignore parts of the document, such as ads or the headlines of other
articles to which the newspaper added a link, that are not part of the news
article.
It turns out that there is a noticeable diﬀerence between text that
appears in prose and text that appears in ads or headlines. Prose has a much
greater frequency of stop words, the very frequent words such as “the” or “and.”
The total number of words that are considered stop words varies with the
application, but it is common to use a list of several hundred of the most
frequent words.
Example 3.24 : A typical ad might say simply “Buy Sudzo.” On the other
hand, a prose version of the same thought that might appear in an article is
“I recommend that you buy Sudzo for your laundry.” In the latter sentence, it
would be normal to treat “I,” “that,” “you,” “for,” and “your” as stop words.
✷
Suppose we deﬁne a shingle to be a stop word followed by the next two
words.
Then the ad “Buy Sudzo” from Example 3.24 has no shingles and
