3.6. THE THEORY OF LOCALITY-SENSITIVE FUNCTIONS
103
i. Mutation, where one symbol is replaced by another symbol. Note that a
mutation can always be performed by an insertion followed by a deletion,
but if we allow mutations, then this change counts for only 1, not 2, when
computing the edit distance.
ii. Transposition, where two adjacent symbols have their positions swapped.
Like a mutation, we can simulate a transposition by one insertion followed
by one deletion, but here we count only 1 for these two steps.
Repeat Exercise 3.5.7 if edit distance is deﬁned to be the number of insertions,
deletions, mutations, and transpositions needed to transform one string into
another.
! Exercise 3.5.9: Prove that the edit distance discussed in Exercise 3.5.8 is
indeed a distance measure.
Exercise 3.5.10: Find the Hamming distances between each pair of the fol-
lowing vectors: 000000, 110011, 010101, and 011100.
3.6
The Theory of Locality-Sensitive Functions
The LSH technique developed in Section 3.4 is one example of a family of func-
tions (the minhash functions) that can be combined (by the banding technique)
to distinguish strongly between pairs at a low distance from pairs at a high dis-
tance. The steepness of the S-curve in Fig. 3.8 reﬂects how eﬀectively we can
avoid false positives and false negatives among the candidate pairs.
Now, we shall explore other families of functions, besides the minhash func-
tions, that can serve to produce candidate pairs eﬃciently. These functions can
apply to the space of sets and the Jaccard distance, or to another space and/or
another distance measure. There are three conditions that we need for a family
of functions:
1. They must be more likely to make close pairs be candidate pairs than
distant pairs. We make this notion precise in Section 3.6.1.
2. They must be statistically independent, in the sense that it is possible to
estimate the probability that two or more functions will all give a certain
response by the product rule for independent events.
3. They must be eﬃcient, in two ways:
(a) They must be able to identify candidate pairs in time much less
than the time it takes to look at all pairs. For example, minhash
functions have this capability, since we can hash sets to minhash
values in time proportional to the size of the data, rather than the
square of the number of sets in the data. Since sets with common
values are colocated in a bucket, we have implicitly produced the
