Database Reference
In-Depth Information
a dataset of 10,000 transactions with 10 items each, where all items participate in
all transactions. Threshold msup was set to 1.0 and all itemsets from the lattice of
the original database were extracted. Then, 2 1-itemsets and 2 4-itemsets, all con-
sisting of disjoint items, were selected to be the sensitive ones and were hidden. To
ensure that the problem had a feasible solution, it was relaxed by using only the
constraints of set S
min
that always lead to a satisfiable CSP. Based on this formula-
tion, the total number of u
nm
variables participating in the problem were 100,000.
To split their products for the 2 4-itemsets, another 20,000 Y
i
variables were in-
troduced. The total number of constraints were 100,004 and the optimal solution
was 99,996 (since 4 items, one belonging in each sensitive itemset, need to be ze-
roed in a transaction). CPLEX was capable of identifying this solution within 889
seconds (approx. 15 min), which is rather low for such a demanding problem. Of
course, adding the constraints from set V increases time complexity. However, in
all conducted experiments the solver was able to rapidly decide if the optimization
problem was infeasible. Thus, in such cases, the relaxation procedure (presented in
Algorithm 14.1) can be applied to allow for the production of a solvable CSP and
the identification of a good approximate hiding solution.
