Database Reference
In-Depth Information
Fig. 2.16
Performing the
second phase of bucketing
The procedure in Fig.
2.15
works by starting with the counts of the 0-1 strings, and
then converts them to strings with 1 and *. The algorithm requires
iterations.
In the
i
th iteration, it increases the counts of all those buckets with a 0 in the
i
th bit,
so that the count now corresponds to a case when that bucket contains a
|
E
(
P
)
|
in that
position. This can be achieved by adding the counts of the buckets with a 0 in the
i
th position to that of the bucket witha1inthat position, with all other bits having
the same value. For example, the count of the string 0*1* is obtained by adding the
counts of the buckets 001* and 011*. In Fig.
2.15
, the process of adding the count
of the bucket
j
to that of the bucket
j
∗
2
i
−
1
achieves this.
The second phase of the bucketing operation requires
+
iterations, and each
iteration requires 2
|
E
(
P
)
|
operations. Therefore, the total time required by the method
is proportional to 2
|
E
(
P
)
|
·|
|
E
(
P
)
|
is sufficiently small, the time required
by the second phase of postprocessing is small compared to the first phase, whereas
the first phase is essentially proportional to reading the database for the current
projection.
We have illustrated the second phase of bucketing by an example in which
E
(
P
)
|
. When
|
E
(
P
)
|
|
|=
3. The process illustrated in Fig.
2.16
illustrates how the second phase of
bucketing is efficiently performed. The exact strings and the corresponding counts
in each of the
E
(
P
)
3 iterations are illustrated. In the first iteration, all those
bits with 0 in the lowest order position have their counts added with the count of
the bitstring witha1inthat position. Thus, 2
|
E
(
P
)
|−
1
|
E
(
P
)
|=
pairwise addition operations
