96
CHAPTER 3. FINDING SIMILAR ITEMS
7. Optionally, if the signatures are suﬃciently similar, go to the documents
themselves and check that they are truly similar, rather than documents
that, by luck, had similar signatures.
3.4.4
Exercises for Section 3.4
Exercise 3.4.1: Evaluate the S-curve 1 −(1 −sr)b for s = 0.1, 0.2, . . ., 0.9, for
the following values of r and b:
• r = 3 and b = 10.
• r = 6 and b = 20.
• r = 5 and b = 50.
! Exercise 3.4.2: For each of the (r, b) pairs in Exercise 3.4.1, compute the
threshold, that is, the value of s for which the value of 1−(1−sr)b is exactly 1/2.
How does this value compare with the estimate of (1/b)1/r that was suggested
in Section 3.4.2?
! Exercise 3.4.3: Use the techniques explained in Section 1.3.5 to approximate
the S-curve 1 −(1 −sr)b when sr is very small.
! Exercise 3.4.4: Suppose we wish to implement LSH by MapReduce. Speciﬁ-
cally, assume chunks of the signature matrix consist of columns, and elements
are key-value pairs where the key is the column number and the value is the
signature itself (i.e., a vector of values).
(a) Show how to produce the buckets for all the bands as output of a single
MapReduce process. Hint: Remember that a Map function can produce
several key-value pairs from a single element.
(b) Show how another MapReduce process can convert the output of (a) to
a list of pairs that need to be compared. Speciﬁcally, for each column i,
there should be a list of those columns j > i with which i needs to be
compared.
3.5
Distance Measures
We now take a short detour to study the general notion of distance measures.
The Jaccard similarity is a measure of how close sets are, although it is not
really a distance measure. That is, the closer sets are, the higher the Jaccard
similarity. Rather, 1 minus the Jaccard similarity is a distance measure, as we
shall see; it is called the Jaccard distance.
However, Jaccard distance is not the only measure of closeness that makes
sense. We shall examine in this section some other distance measures that have
applications. Then, in Section 3.6 we see how some of these distance measures
