Parallelization Framework for Exact Hiding - Association Rule Hiding for Data Mining - page 116

Fig. 17.5: Three-way decomposition using weighted graph partitioning.
17.1.2.2 Decomposition Using Weighted Graph Partitioning
A serious disadvantage of decomposition using articulation points is the fact that
it provides very limited control over (i) the number of components in which the
CSP will eventually split, and (ii) the size of each of these components. This fact
may lead to a low CPUs utilization in a parallel solving environment. For this rea-
son, [25] proposes an alternative decomposition strategy that can be employed to
break the original CSP into as many CSPs as necessary, based on the number of
available processors. The proposed decomposition strategy relies on modern graph
partitioning algorithms to provide an optimal decomposition.
The decomposition strategy operates as follows. A constraints graph is generated
by assigning each u nm variable of the original CSP to a vertex and each constraint
c to a number of edges e c formulating a clique in the graph (while denoting the de-
pendence of the u nm variables involved). This graph, henceforth denoted as G W , is
a weighted alternative of graph G and is associated with two types of weights: one
for each vertex u2V W and one for each edge e2E W . The weight of a vertex corre-
sponds to the number of constraints in which it participates in the CSP. The weight
of an edge, on the other hand, reflects the number of constraints in the CSP in which
the two vertexes (it connects) appear together. Using a weighted graph partitioning