106
CHAPTER 3. FINDING SIMILAR ITEMS
candidate pair if every one of the r rows in the band say that x and y are equal
(and therefore a candidate pair according to that row).
Since the members of F are independently chosen to make a member of F′,
we can assert that F′ is a
d1, d2, (p1)r, (p2)r
-sensitive family. That is, for any
p, if p is the probability that a member of F will declare (x, y) to be a candidate
pair, then the probability that a member of F′ will so declare is pr.
There is another construction, which we call the OR-construction, that turns
a (d1, d2, p1, p2)-sensitive family F into a
d1, d2, 1 −(1 −p1)b, 1 −(1 −p2)b
-
sensitive family F′. Each member f of F′ is constructed from b members of F,
say f1, f2, . . . , fb. We deﬁne f(x) = f(y) if and only if fi(x) = fi(y) for one or
more values of i. The OR-construction mirrors the eﬀect of combining several
bands: x and y become a candidate pair if any band makes them a candidate
pair.
If p is the probability that a member of F will declare (x, y) to be a candidate
pair, then 1−p is the probability it will not so declare. (1−p)b is the probability
that none of f1, f2, . . . , fb will declare (x, y) a candidate pair, and 1 −(1 −p)b
is the probability that at least one fi will declare (x, y) a candidate pair, and
therefore that f will declare (x, y) to be a candidate pair.
Notice that the AND-construction lowers all probabilities, but if we choose F
and r judiciously, we can make the small probability p2 get very close to 0, while
the higher probability p1 stays signiﬁcantly away from 0. Similarly, the OR-
construction makes all probabilities rise, but by choosing F and b judiciously,
we can make the larger probability approach 1 while the smaller probability
remains bounded away from 1. We can cascade AND- and OR-constructions in
any order to make the low probability close to 0 and the high probability close
to 1. Of course the more constructions we use, and the higher the values of r
and b that we pick, the larger the number of functions from the original family
that we are forced to use. Thus, the better the ﬁnal family of functions is, the
longer it takes to apply the functions from this family.
Example 3.19 : Suppose we start with a family F. We use the AND-construc-
tion with r = 4 to produce a family F1. We then apply the OR-construction
to F1 with b = 4 to produce a third family F2. Note that the members of F2
each are built from 16 members of F, and the situation is analogous to starting
with 16 minhash functions and treating them as four bands of four rows each.
The 4-way AND-function converts any probability p into p4.
When we
follow it by the 4-way OR-construction, that probability is further converted
into 1−(1−p4)4. Some values of this transformation are indicated in Fig. 3.11.
This function is an S-curve, staying low for a while, then rising steeply (although
not too steeply; the slope never gets much higher than 2), and then leveling
oﬀat high values. Like any S-curve, it has a ﬁxedpoint, the value of p that is
left unchanged when we apply the function of the S-curve. In this case, the
ﬁxedpoint is the value of p for which p = 1 −(1 −p4)4. We can see that the
ﬁxedpoint is somewhere between 0.7 and 0.8. Below that value, probabilities are
decreased, and above it they are increased. Thus, if we pick a high probability
