Databases Reference
In-Depth Information
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 positives.
2
Example 3.20 : We can cascade constructions as much as we like. For exam-
ple, 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.99999996, 0.0008715)-sensitive family.
2
3.6.4 Exercises for Section 3.6
Exercise 3.6.1 : What is the effect on probability of starting with the family
of minhash functions and applying:
(a) A 2-way AND construction followed by a 3-way OR construction.
(b) A 3-way OR construction followed by a 2-way AND construction.
(c) A 2-way AND construction followed by a 2-way OR construction, followed
by a 2-way AND construction.
(d) A 2-way OR construction followed by a 2-way AND construction, followed
by a 2-way OR construction followed by a 2-way AND construction.
Exercise 3.6.2 : Find the fixedpoints for each of the functions constructed in
Exercise 3.6.1.
! Exercise 3.6.3 : Any function of probability p, such as that of Fig. 3.10, has
a slope given by the derivative of the function. The maximum slope is where
that derivative is a maximum. Find the value of p that gives a maximum slope
for the S-curves given by Fig. 3.10 and Fig. 3.11. What are the values of these
maximum slopes?
!! Exercise 3.6.4 : Generalize Exercise 3.6.3 to give, as a function of r and b, the
point of maximum slope and the value of that slope, for families of functions
defined from the minhash functions by:
(a) An r-way AND construction followed by a b-way OR construction.
(b) A b-way OR construction followed by an r-way AND construction.
