3.6. THE THEORY OF LOCALITY-SENSITIVE FUNCTIONS
107
p
1 −(1 −p4)4
0.2
0.0064
0.3
0.0320
0.4
0.0985
0.5
0.2275
0.6
0.4260
0.7
0.6666
0.8
0.8785
0.9
0.9860
Figure 3.11: Eﬀect of the 4-way AND-construction followed by the 4-way OR-
construction
above the ﬁxedpoint and a low probability below it, we shall have the desired
eﬀect that the low probability is decreased and the high probability is increased.
Suppose F is the minhash functions, regarded as a (0.2, 0.6, 0.8, 0.4)-sens-
itive family. Then F2, the family constructed by a 4-way AND followed by a
4-way OR, is a (0.2, 0.6, 0.8785, 0.0985)-sensitive family, as we can read from the
rows for 0.8 and 0.4 in Fig. 3.11. By replacing F by F2, we have reduced both
the false-negative and false-positive rates, at the cost of making application of
the functions take 16 times as long.
✷
p
1 −(1 −p)44
0.1
0.0140
0.2
0.1215
0.3
0.3334
0.4
0.5740
0.5
0.7725
0.6
0.9015
0.7
0.9680
0.8
0.9936
Figure 3.12: Eﬀect of the 4-way OR-construction followed by the 4-way AND-
construction
Example 3.20 : For the same cost, we can apply a 4-way OR-construction
followed by a 4-way AND-construction. Figure 3.12 gives the transformation
on probabilities implied by this construction. For instance, suppose that F is a
(0.2, 0.6, 0.8, 0.4)-sensitive family. Then the constructed family is a
(0.2, 0.6, 0.9936, 0.5740)-sensitive
