Database Reference
In-Depth Information
Chapter 17
Parallelization Framework for Exact Hiding
In this chapter, we elaborate on a novel framework, introduced in [25], that is suit-
able for decomposition and parallelization of the exact hiding algorithms that were
covered in Chapters 14, 15 and 16. The framework operates in three phases to de-
compose CSPs that are produced by the exact hiding algorithms, into a set of smaller
CSPs that can be solved in parallel. In the first phase, the original CSP is structurally
decomposed into a set of independent CSPs, each of which is assigned to a different
processor. In the second phase, for each independent CSP a decision is made on
whether it should be further decomposed into a set of dependent CSPs, through a
function that questions the gain of any further decomposition. In the third and last
step, the solutions of the various CSPs, produced as part of the decomposition pro-
cess, are appropriately combined to provide the solution of the original CSP (i.e.
the one prior to the decomposition). The generality of the framework allows it to
efficiently handle any CSP that consists of linear constraints involving binary vari-
ables and whose objective is to maximize (or minimize) the summation of these
variables. Together with existing approaches for the parallel mining of association
rules [6, 34, 80], the framework of [25] can be applied to parallelize the most time
consuming steps of the exact hiding algorithms.
The remainder of this chapter is structured as follows: In Section 17.1 we present
the properties of the parallelization framework. Then, Section 17.2 contains the ex-
perimental evaluation and demonstrates the benefit of using this framework towards
speeding up the hiding process.
17.1 The Parallelization Framework
Performing knowledge hiding by using the inline [23], the two-phase iterative [27]
or the hybrid approach [26] allows for the identification of exact hiding solutions,
whenever such solutions exist. However, the cost of identifying an exact hiding so-
lution is usually high due to the time required for solving the involved CSP.
