Database Reference
In-Depth Information
Algorithm 11.1 The Max-Min 1 Algorithm of Moustakides & Verykios [50, 51].
1: function M
AX
-M
IN
1(Original database D
O
, revised positive border Bd
+
, sensitive itemsets
S, minimum support threshold msup)
D
0
D
O
2:
3:
while S 6=? do
4:
Select I 2 S with minimum support, breaking ties in favor of maximum length
For each tentative victim item j 2 I compute its tentative victim itemsets Bd
+
j
j
5:
6:
while sup(I;D
0
) msup do
7:
Compute the max-min itemset, splitting ties arbitrarily
8:
Remove victim item i 2 I, determined by the max-min itemset from the first
transaction that supports the sensitive itemset I
9: Revise the tentative victim itemsets
10: end while
11: Remove I from S
12: end while
13: Return: sanitized database D D
0
14: end function
minimum support itemsets from Bd
+
j
j
(for each j 2 I) and selects to remove the
victim item i 2 I (corresponding to the set Bd
+
j
i
) that is determined by the current
max-min itemset, from the first transaction in the database that supports the sensi-
tive itemset I. In the case that the max-min itemset participates to more than one
tentative victim itemsets and different victim items can be used for the hiding of the
sensitive itemset, Max-Min 1 arbitrarily selects the tentative victim item to use for
hiding. After removing the victim item from a transaction that supports the selected
sensitive itemset, the algorithm revises the affected sets of tentative victim itemsets
Bd
+
j
i
and proceeds to the next iteration until the itemset is hidden. The same pro-
cess repeats until all the sensitive itemsets in S are hidden from D
O
, at which point
the sanitized database D is returned. Algorithm 11.1 straightens out the operation
of the Max-Min 1 algorithm.
11.4 Max-Min 2 Algorithm
The Max-Min 2 algorithm provides a more sophisticated approach to knowledge
hiding than that of Max-Min 1, by reducing the side-effects of the hiding process to
the nonsensitive itemsets. While the basic features of Max-Min 1 are also adopted
by Max-Min 2, this algorithm takes special care in improving the selection process
for the transactions of the original database that will be sanitized to accommodate
the hiding of the sensitive knowledge. On these grounds, three special case scenarios
that are based on the properties of the identified max-min itemsets, are taken into
consideration by Max-Min 2, and are discussed in the following.
The first case scenario regards the existence of more than one max-min itemsets,
which are all derived from the same tentative victim item j. In this case scenario,
Max-Min 2 tries to reduce the support of the sensitive itemset through j, without
