Database Reference
In-Depth Information
Algorithm 11.2 The Max-Min 2 Algorithm of Moustakides & Verykios [50, 51].
1: function M
AX
-M
IN
2(Original database D
O
, revised positive border Bd
+
, sensitive itemsets
S, minimum support threshold msup)
2: D
0
D
O
3: while S 6=? do
4: Select I 2 S with minimum support, breaking ties in favor of maximum length
5: For each tentative victim item j 2 I compute its tentative victim itemsets Bd
+
j
j
6: while sup(I;D
0
) msup do
7: Compute the max-min itemset, splitting ties arbitrarily
8: if 9j 2 I : max-min Bd
+
j
j
and 8i 6= j : Bd
+
j
i
\max-min =? then
9: if L L
I
L
U
6=? then
10:
delete j from a transaction of list L
11: else
12: delete j from a transaction of list L
I
13: end if
14: else
15: K ftentative victim items j 2 I : Bd
+
j
j
\ max-min 6=?g
16: for each k 2 K do
17: U max-min \Bd
+
j
k
18: if L L
I
L
U
6=? then
19: delete k from a transaction of list L
20: break
21: end if
22: end for
23: if L =? then
24: for each k
1
2 K do
25: for each k
2
(6= k
1
) 2 K do
26: U
1
max-min \Bd
+
j
k
1
27: U
2
max-min \Bd
+
j
k
2
28: L (L
U
1
\L
I
)(L
U
2
\L
I
)
29: if L 6=? then
30: delete k
1
from a transaction of list L
31: else
32: delete k
1
from a transaction of list L
U
1
\L
I
33: end if
34: end for
35: end for
36: end if
37: end if
38: end while
39: Remove I from S
40: end while
41: Return: sanitized database D D
0
42: end function