3.4. LOCALITY-SENSITIVE HASHING FOR DOCUMENTS
91
(c) How close are the estimated Jaccard similarities for the six pairs of columns
to the true Jaccard similarities?
! Exercise 3.3.4: Now that we know Jaccard similarity is related to the proba-
bility that two sets minhash to the same value, reconsider Exercise 3.1.3. Can
you use this relationship to simplify the problem of computing the expected
Jaccard similarity of randomly chosen sets?
! Exercise 3.3.5: Prove that if the Jaccard similarity of two columns is 0, then
minhashing always gives a correct estimate of the Jaccard similarity.
!! Exercise 3.3.6: One might expect that we could estimate the Jaccard simi-
larity of columns without using all possible permutations of rows. For example,
we could only allow cyclic permutations; i.e., start at a randomly chosen row
r, which becomes the ﬁrst in the order, followed by rows r + 1, r + 2, and so
on, down to the last row, and then continuing with the ﬁrst row, second row,
and so on, down to row r −1. There are only n such permutations if there are
n rows. However, these permutations are not suﬃcient to estimate the Jaccard
similarity correctly. Give an example of a two-column matrix where averaging
over all the cyclic permutations does not give the Jaccard similarity.
! Exercise 3.3.7: Suppose we want to use a MapReduce framework to compute
minhash signatures. If the matrix is stored in chunks that correspond to some
columns, then it is quite easy to exploit parallelism. Each Map task gets some
of the columns and all the hash functions, and computes the minhash signatures
of its given columns. However, suppose the matrix were chunked by rows, so
that a Map task is given the hash functions and a set of rows to work on. Design
Map and Reduce functions to exploit MapReduce with data in this form.
! Exercise 3.3.8: As we noticed in Section 3.3.6, we have problems when a
column has only 0’s. If we compute a minhash function using entire columns
(as in Section 3.3.2), then the only time we get all 0’s in a column is if that
column represents the empty set. How should we handle the empty set to make
sure no errors in Jaccard-similarity estimation are introduced?
!! Exercise 3.3.9: In Example 3.9, each of the three estimates of Jaccard sim-
ilarity we obtained was either smaller than or the same as the true Jaccard
similarity. Is it possible that for another pair of columns, the average of the
Jaccard similarities of the upper and lower halves will exceed the actual Jaccard
similarity of the columns?
3.4
Locality-Sensitive Hashing for Documents
Even though we can use minhashing to compress large documents into small
signatures and preserve the expected similarity of any pair of documents, it
still may be impossible to ﬁnd the pairs with greatest similarity eﬃciently. The
