3.2. SHINGLING OF DOCUMENTS
79
3.2.2
Choosing the Shingle Size
We can pick k to be any constant we like. However, if we pick k too small, then
we would expect most sequences of k characters to appear in most documents.
If so, then we could have documents whose shingle-sets had high Jaccard simi-
larity, yet the documents had none of the same sentences or even phrases. As
an extreme example, if we use k = 1, most Web pages will have most of the
common characters and few other characters, so almost all Web pages will have
high similarity.
How large k should be depends on how long typical documents are and how
large the set of typical characters is. The important thing to remember is:
• k should be picked large enough that the probability of any given shingle
appearing in any given document is low.
Thus, if our corpus of documents is emails, picking k = 5 should be ﬁne.
To see why, suppose that only letters and a general white-space character ap-
pear in emails (although in practice, most of the printable ASCII characters
can be expected to appear occasionally).
If so, then there would be 275 =
14,348,907 possible shingles. Since the typical email is much smaller than 14
million characters long, we would expect k = 5 to work well, and indeed it does.
However, the calculation is a bit more subtle. Surely, more than 27 charac-
ters appear in emails, However, all characters do not appear with equal proba-
bility. Common letters and blanks dominate, while ”z” and other letters that
have high point-value in Scrabble are rare. Thus, even short emails will have
many 5-shingles consisting of common letters, and the chances of unrelated
emails sharing these common shingles is greater than would be implied by the
calculation in the paragraph above. A good rule of thumb is to imagine that
there are only 20 characters and estimate the number of k-shingles as 20k. For
large documents, such as research articles, choice k = 9 is considered safe.
3.2.3
Hashing Shingles
Instead of using substrings directly as shingles, we can pick a hash function
that maps strings of length k to some number of buckets and treat the resulting
bucket number as the shingle. The set representing a document is then the
set of integers that are bucket numbers of one or more k-shingles that appear
in the document. For instance, we could construct the set of 9-shingles for a
document and then map each of those 9-shingles to a bucket number in the
range 0 to 232 −1. Thus, each shingle is represented by four bytes instead
of nine. Not only has the data been compacted, but we can now manipulate
(hashed) shingles by single-word machine operations.
Notice that we can diﬀerentiate documents better if we use 9-shingles and
hash them down to four bytes than to use 4-shingles, even though the space used
to represent a shingle is the same. The reason was touched upon in Section 3.2.2.
If we use 4-shingles, most sequences of four bytes are unlikely or impossible to
