3.3. SIMILARITY-PRESERVING SUMMARIES OF SETS
81
Exercise 3.2.2: If we use the stop-word-based shingles of Section 3.2.4, and
we take the stop words to be all the words of three or fewer letters, then what
are the shingles in the ﬁrst sentence of Section 3.2?
Exercise 3.2.3: What is the largest number of k-shingles a document of n
bytes can have? You may assume that the size of the alphabet is large enough
that the number of possible strings of length k is at least n.
3.3
Similarity-Preserving Summaries of Sets
Sets of shingles are large. Even if we hash them to four bytes each, the space
needed to store a set is still roughly four times the space taken by the document.
If we have millions of documents, it may well not be possible to store all the
shingle-sets in main memory.3
Our goal in this section is to replace large sets by much smaller represen-
tations called “signatures.” The important property we need for signatures is
that we can compare the signatures of two sets and estimate the Jaccard sim-
ilarity of the underlying sets from the signatures alone. It is not possible that
the signatures give the exact similarity of the sets they represent, but the esti-
mates they provide are close, and the larger the signatures the more accurate
the estimates. For example, if we replace the 200,000-byte hashed-shingle sets
that derive from 50,000-byte documents by signatures of 1000 bytes, we can
usually get within a few percent.
3.3.1
Matrix Representation of Sets
Before explaining how it is possible to construct small signatures from large
sets, it is helpful to visualize a collection of sets as their characteristic matrix.
The columns of the matrix correspond to the sets, and the rows correspond to
elements of the universal set from which elements of the sets are drawn. There
is a 1 in row r and column c if the element for row r is a member of the set for
column c. Otherwise the value in position (r, c) is 0.
Element
S1
S2
S3
S4
a
1
0
0
1
b
0
0
1
0
c
0
1
0
1
d
1
0
1
1
e
0
0
1
0
Figure 3.2: A matrix representing four sets
3There is another serious concern: even if the sets ﬁt in main memory, the number of pairs
may be too great for us to evaluate the similarity of each pair. We take up the solution to
this problem in Section 3.4.
