Database Reference
In-Depth Information
minimize (x 1 +x 2 +x 4 +x 5 )
8
<
:
x 1 +x 5 1
x 1 +x 4 +x 5 3
x 2 +x 4 2
x 1 ; x 2 ; x 4 ; x 5 2f0; 1g
subject to
Fig. 13.4: The second independent block for the CSP of Figure 13.2.
Algorithm 13.1 The Decomposition Algorithm proposed in [47].
1: function D ECOMPOSE (Database D S , sensitive itemsets S)
2:
for each itemset I 2S do
3:
C(I) fIg
. Initially every sensitive itemset belongs to a separate block
4:
p j j
. j is the position of I in the (arbitrary) ordering of the itemsets in S
5: end for
6: for each transaction T i 2D S do
7: r p k where k is the index of the first nonzero value in M for T i
8: for the rest nonzero elements of T i in M do
9: C(I r ) C(I r )[C(I p j )
10: C(I p j ) ?
11: p j r
12: end for
13: end for
14: Return: nonempty independent blocks C(I)
15: end function
algorithm operates in time that is linear with respect to the number of supporting
transactions for the sensitive itemsets.
To illustrate the operation of this algorithm, consider the example of Table 13.1
that involves 5 sensitive itemsets (with constraints c 1 : : : c 5 ) which are supported by
a total of 7 transactions. As a preprocessing step, Algorithm 13.1 (lines 3-4) con-
siders that each sensitive itemset belongs to a different independent block, thus we
have that: C(I 1 ) =fI 1 g; : : : ;C(I 5 ) =fI 5 g. The indexing pointers p are accordingly
updated based on the constraints of matrix M, i.e. p 1 = 1; p 2 = 3; p 3 = 2; p 4 =
5; p 5 = 4. At this point we enter the first iteration of the algorithm, which involves
transaction T 6 . The first nonzero element in the column of T 6 is that for c 1 and thus
we have k = r = 1. Since there is no other nonzero element for T 6 we proceed to the
next iteration of the algorithm, which involves transaction T 7 . For this transaction we
have r = p 1 = 1. Since the next element of transaction T 7 is nonzero, we have that
C(I 1 ) C(I 1 )[C(I 3 ) =fI 1 ; I 3 g(since p 2 = 3) and then C(I 3 ) ?; p 2 1. Follow-
ing that, we move to T 3 which again has only one nonzero element and thus requires
no special handling. Next, for T 1 we have that r p 3 = 2 and C(I 2 ) =fI 2 ; I 5 g. In
the same way, Algorithm 13.1 identifies that the constraints-by-transactions matrix
M of Figure 13.1 can be decomposed into two independent blocks: fc 1 ; c 3 g (cor-
 
 
Search WWH ::




Custom Search