3.10. SUMMARY OF CHAPTER 3
131
✦Minhash Signatures: We may represent sets by picking some list of per-
mutations and computing for each set its minhash signature, which is the
sequence of minhash values obtained by applying each permutation on the
list to that set. Given two sets, the expected fraction of the permutations
that will yield the same minhash value is exactly the Jaccard similarity
of the sets.
✦Eﬃcient Minhashing: Since it is not really possible to generate random
permutations, it is normal to simulate a permutation by picking a random
hash function and taking the minhash value for a set to be the least hash
value of any of the set’s members. An additional eﬃciency can be had
by restricting the search for the smallest minhash value to only a small
subset of the universal set.
✦Locality-Sensitive Hashing for Signatures: This technique allows us to
avoid computing the similarity of every pair of sets or their minhash sig-
natures. If we are given signatures for the sets, we may divide them into
bands, and only measure the similarity of a pair of sets if they are identi-
cal in at least one band. By choosing the size of bands appropriately, we
can eliminate from consideration most of the pairs that do not meet our
threshold of similarity.
✦Distance Measures: A distance measure is a function on pairs of points in
a space that satisfy certain axioms. The distance between two points is 0 if
the points are the same, but greater than 0 if the points are diﬀerent. The
distance is symmetric; it does not matter in which order we consider the
two points. A distance measure must satisfy the triangle inequality: the
distance between two points is never more than the sum of the distances
between those points and some third point.
✦Euclidean Distance: The most common notion of distance is the Euclidean
distance in an n-dimensional space. This distance, sometimes called the
L2-norm, is the square root of the sum of the squares of the diﬀerences
between the points in each dimension. Another distance suitable for Eu-
clidean spaces, called Manhattan distance or the L1-norm is the sum of
the magnitudes of the diﬀerences between the points in each dimension.
✦Jaccard Distance: One minus the Jaccard similarity is a distance measure,
called the Jaccard distance.
✦Cosine Distance: The angle between vectors in a vector space is the cosine
distance measure. We can compute the cosine of that angle by taking the
dot product of the vectors and dividing by the lengths of the vectors.
✦Edit Distance: This distance measure applies to a space of strings, and
is the number of insertions and/or deletions needed to convert one string
into the other. The edit distance can also be computed as the sum of
