90
CHAPTER 3. FINDING SIMILAR ITEMS
similarity of 0, while the bottom half represents sets with a Jaccard similarity
1/3. The expected number of matches in the signatures of S1 and S3 is therefore
the average of these, or 1/6. That compares with the true Jaccard similarity
SIM(S1, S3) = 1/5. Finally, when we compare S2 and S3, we note that the
Jaccard similarity of these columns in the ﬁrst four rows is 1/2, and so is their
Jaccard similarity in the bottom four rows. The average, 1/2, also agrees exactly
with SIM(S2, S3) = 1/2.
✷
3.3.8
Exercises for Section 3.3
Exercise 3.3.1: Verify the theorem from Section 3.3.3, which relates the Jac-
card similarity to the probability of minhashing to equal values, for the partic-
ular case of Fig. 3.2.
(a) Compute the Jaccard similarity of each of the pairs of columns in Fig. 3.2.
! (b) Compute, for each pair of columns of that ﬁgure, the fraction of the 120
permutations of the rows that make the two columns hash to the same
value.
Exercise 3.3.2: Using the data from Fig. 3.4, add to the signatures of the
columns the values of the following hash functions:
(a) h3(x) = 2x + 4 mod 5.
(b) h4(x) = 3x −1 mod 5.
Element
S1
S2
S3
S4
0
0
1
0
1
1
0
1
0
0
2
1
0
0
1
3
0
0
1
0
4
0
0
1
1
5
1
0
0
0
Figure 3.6: Matrix for Exercise 3.3.3
Exercise 3.3.3: In Fig. 3.6 is a matrix with six rows.
(a) Compute the minhash signature for each column if we use the following
three hash functions: h1(x) = 2x + 1 mod 6; h2(x) = 3x + 2 mod 6;
h3(x) = 5x + 2 mod 6.
(b) Which of these hash functions are true permutations?
