Database Reference
In-Depth Information
tive values for C
A;00
and C
B;00
were found. The objective value for problem instance
C
00
will then be the summation of these two objectives. To calculate the overall ob-
jective value and identify the solution of the original CSP, one needs to identify the
maximum among the objective values of all problem instances. An example of par-
allel solving after the application of a decomposition strategy is presented in Figure
17.6,
where it is easy to notice that the solution of the initial CSP is provided by
examining, for all involved CSPs, the two potential values of the selected cut-vertex
h (i.e., solving each CSP for h = 0 and h = 1). The overall objective corresponds
to the maximum of the two objectives, an argument that is justified by the binary
nature of variable h.
17.2 Computational Experiments and Results
In this section, we provide the results of a set of experiments that were conducted
in [25] to test the structural decomposition phase of the presented parallelization
framework. The parallelization framework was tested using CSPs produced by the
inline approach of [23], when it was applied to hide sensitive knowledge coming
from three real datasets, summarized in Table 14.4. In all tested settings, the thresh-
olds of minimum support were properly selected to ensure an adequate amount of
frequent itemsets and the sensitive itemsets to be hidden were selected randomly
among the frequent ones. Several experiments were conducted for the hiding of sen-
sitive 2-itemsets, 3-itemsets, and 4-itemsets. All experiments were conducted on a
PC running Linux on an Intel Pentium D, 3.2 Ghz processor equipped with 4 GB of
main memory. All integer programs were solved using ILOG CPLEX 9.0 [36].
All presented experiments assume the existence of the necessary resources that
would lead to a full-scale parallelization of the initial CSP. This means that if the
original CSP can potentially break into P independent parts, then the assumption is
that at least P processors are available to independently undertake and solve each
resultant CSP. Thus, the overall runtime of the hiding algorithm will equal the sum-
mation of (i) the runtime of the serial algorithm that produced the original CSP,
(ii) the runtime of the Structure Identification Algorithm (SIA) that decomposed the
original CSP into numerous independent parts, (iii) the time that is needed to com-
municate each of the resulting CSPs to an available processor, (iv) the time needed
to solve the largest of these CSPs, (v) the communication time needed to return the
attained solutions to the original processor (hereon called “master”) that held the
whole problem, and finally (vi) the time needed by the master processor to calcu-
late the summation of the objective values returned in order to compute the overall
solution of the problem. That is:
T
overall
= T
HA
+T
SIA
+T
spread
+T
solve
+T
gather
+T
aggregate
(17.5)
The following experiments capture the runtime of (ii) and (iv), namely T
SIA
and
T
solve
, since the communication overhead (T
spread
+ T
gather
) and the overall so-
