Database Reference
In-Depth Information
11.2 Order of Hiding Itemsets
Given a set of sensitive itemsets, the order in which these itemsets are hidden may
have a significant impact on the quality of the sanitized database. Thus, when hid-
ing multiple sensitive itemsets, the proposed Max-Min algorithms operate by first
sorting the sensitive itemsets in ascending order of support and then by hiding each
sensitive itemset in a one-by-one fashion, starting from the itemset that is least sup-
ported in the original database D
O
. The rationale behind the selected order is that
sensitive itemsets with a low support are easier to hide as they are already positioned
closer to the borderline than their higher support counterparts.
An interesting observation (proven in [51]) is that while the sensitive itemset with
the minimum support is hidden, its support constantly remains lower than the sup-
port of the rest of the sensitive itemsets in the database. This behavior is attributed
to the fact that the Max-Min algorithms decrease the support of the sensitive item-
set that is selected for hiding by one, in each iteration, as they operate by deleting
the victim item from one transaction of the database. As a result, the support of any
other sensitive itemsets may lower by at most one in each iteration of the algorithm,
if the corresponding sensitive itemsets are affected by the employed item deletion.
Still, however, the support of these itemsets will continue to be higher than that of
the currently selected sensitive itemset. Even so, the original ordering of the sensi-
tive itemsets in terms of support can be significantly affected during the sanitization
process. This is because the support of the sensitive itemsets that are not yet se-
lected for hiding may change to a different degree based on the victim items that
are selected by the hiding algorithm and the transactions from which these items are
deleted. Consequently, the Max-Min algorithms need to recompute the supports of
all the remaining sensitive itemsets after hiding the currently selected itemset and
choose to hide the sensitive itemset that has the new minimum value of support.
Last, in the case of a tie among the sensitive itemsets in terms of support, the
Max-Min algorithms operate by giving preference to the hiding of longer sensitive
itemsets than shorter ones. This preference is justified by the authors on the grounds
of the degree of freedom that such a choice bestows for the selection of the victim
item, among the tentative ones.
11.3 Max-Min 1 Algorithm
Max-Min 1 is a straightforward heuristic algorithm that applies the max-min cri-
terion for the hiding of the sensitive itemsets. Until all the sensitive itemsets are
hidden from D
O
, the algorithm selects the sensitive itemset I that currently has the
minimum value of support (breaking ties in favor of maximum length) and for each
tentative victim item j 2 I of this itemset, it computes the tentative victim itemsets
Bd
+
j
j
from the revised positive border Bd
+
. Then, Max-Min 1 undergoes a series
of iterations until the selected sensitive itemset is properly hidden in the database.
In each iteration, the algorithm computes the current max-min itemset using the
