Database Reference
In-Depth Information
minimize
å
T
n
2D
S
x
i
(
å
T
n
2D
S
a
i j
x
i
sup(I;D
O
)msup+1; 8I 2S
x
i
2f0; 1g;
subject to
8i 2D
O
Fig. 13.1: CSP formulation for the exact part of Menon's algorithm [47].
the sensitive itemsets and subsequently solving it through the application of integer
programming. The goal of the formulated CSP is to maximize the accuracy of the
produced sanitized database by identifying the minimum number of transactions that
need to be modified to hide the sensitive knowledge. Apart from the formulation of
the CSP, in this section we also shed light on a decomposition approach that was
proposed in [47] to improve the efficiency of its solving. Following that, Section
13.2 delivers two simple heuristic strategies that can be used to perform the actual
hiding of the sensitive itemsets from the original database.
13.1 Exact Part
In this section we shed light on the exact part of Menon's algorithm [47], which
involves the formulation of a constraints satisfaction problem. The solution of this
CSP will provide the minimum number of transactions from the original database
that have to be sanitized to conceal the sensitive knowledge. In what follows, Section
13.1.1 elaborates on the properties of the CSP and provides its formulation. After
formulating the CSP, an integer programming solver, such as ILOG CPLEX [36],
GNU GLPK [29] or XPRESS-MP [32] can be used to solve it and derive the objec-
tive function along with the values of the participating variables. Since the produced
CSP may involve too many constraints and reduces to the set-covering problem [47],
thus is NP-complete [22], Section 13.1.2 delivers a decomposition approach that can
be employed in certain cases to improve the runtime of solving the CSP and enhance
the efficiency of the hiding algorithm.
13.1.1 CSP Formulation
The goal of the exact part of Menon's algorithm [47] is to identify the minimum
number of transactions from the original database D
O
that have to be sanitized so
that every sensitive itemset is hidden in database D. As is evident, the minimum
number of transactions that have to be sanitized for the hiding of a sensitive itemset
is equal to the current support that this itemset has in the database minus the mini-
mum support threshold plus one. When this number of transactions no longer sup-
