130
CHAPTER 3. FINDING SIMILAR ITEMS
Exercise 3.9.2: Suppose we ﬁlter candidate pairs based only on length, as in
Section 3.9.3. If s is a string of length 20, with what strings is s compared when
J, the lower bound on Jaccard similarity has the following values: (a) J = 0.85
(b) J = 0.95 (c) J = 0.98?
Exercise 3.9.3: Suppose we have a string s of length 15, and we wish to index
its preﬁx as in Section 3.9.4.
(a) How many positions are in the preﬁx if J = 0.85?
(b) How many positions are in the preﬁx if J = 0.95?
! (c) For what range of values of J will s be indexed under its ﬁrst four symbols,
but no more?
Exercise 3.9.4: Suppose s is a string of length 12. With what symbol-position
pairs will s be compared with if we use the indexing approach of Section 3.9.5,
and (a) J = 0.75 (b) J = 0.95?
! Exercise 3.9.5: Suppose we use position information in our index, as in Sec-
tion 3.9.5. Strings s and t are both chosen at random from a universal set of
100 elements. Assume J = 0.9. What is the probability that s and t will be
compared if
(a) s and t are both of length 9.
(b) s and t are both of length 10.
Exercise 3.9.6: Suppose we use indexes based on both position and suﬃx
length, as in Section 3.9.6. If s is a string of length 20, with what symbol-
position-length triples will s be compared with, if (a) J = 0.8 (b) J = 0.9?
3.10
Summary of Chapter 3
✦Jaccard Similarity: The Jaccard similarity of sets is the ratio of the size
of the intersection of the sets to the size of the union. This measure of
similarity is suitable for many applications, including textual similarity of
documents and similarity of buying habits of customers.
✦Shingling: A k-shingle is any k characters that appear consecutively in
a document. If we represent a document by its set of k-shingles, then
the Jaccard similarity of the shingle sets measures the textual similarity
of documents. Sometimes, it is useful to hash shingles to bit strings of
shorter length, and use sets of hash values to represent documents.
✦Minhashing: A minhash function on sets is based on a permutation of the
universal set. Given any such permutation, the minhash value for a set is
that element of the set that appears ﬁrst in the permuted order.
