Finding Similar Items - Mining of Massive Datasets - page 98

Figure 3.10 Effect of the 4-way AND-construction followed by the 4-way OR-construction

Suppose F is the minhash functions, regarded as a (0 . 2 , 0 . 6 , 0 . 8 , 0 . 4)-sensitive family.
Then F 2 , 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.10 .
By replacing F with F 2 , 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.

□

EXAMPLE 3.19 For the same cost, we can apply a 4-way OR-construction followed by a
4-way AND-construction. Figure 3.11 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

family. This choice is not necessarily the best. Although the higher probability has moved
much closer to 1, the lower probability has also raised, increasing the number of false pos-
itives. □

Figure 3.11 Effect of the 4-way OR-construction followed by the 4-way AND-construction

EXAMPLE 3.20 We can cascade constructions as much as we like. For example, we could
use the construction of Example 3.18 on the family of minhash functions and then use the
construction of Example 3.19 on the resulting family. The constructed family would then
have functions each built from 256 minhash functions. It would, for instance transform a
(0 . 2 , 0 . 8 , 0 . 8 , 0 . 2)-sensitive family into a (0 . 2 , 0 . 8 , 0 . 9991285 , 0 . 0000004)-sensitive fam-
ily. □