Database Reference
In-Depth Information
Chapter 15
Two-Phase Iterative Algorithm
In this chapter, we present a two-phase iterative algorithm (proposed in [27]) that
extends the functionality of the inline algorithm of [23] (Chapter 14) to allow for the
identification of exact hiding solutions for a wider spectrum of problem instances.
A problem instance is defined as the set of (i) the original dataset D
O
, (ii) the mini-
mum frequency threshold mfreq that is considered for its mining, and (iii) the set of
sensitive itemsets S that have to be protected. Since the inline algorithm allows only
supported items in D
O
to become unsupported in D, there exist problem instances
that although they allow for an exact hiding solution, the inline approach is incapable
of finding it. The truthfulness of this statement can be observed in the experiments
provided in Section 15.4, as well as in the experimental evaluation of [26].
The remainder of this chapter is organized as follows. In Section 15.1 we present
the theoretical background behind the two-phase iterative process (see
Figure 15.1;
large box shows the iteration). Section 15.2 highlights some important aspects of
the methodology that influence the quality of the hiding solution that is found. In
Section 15.3, we present a specific problem instance for which the inline algorithm
fails to provide an exact hiding solution and demonstrate how the two-phase itera-
tive algorithm achieves to identify it. Finally, Section 15.4 presents the experimental
evaluation of the two-phase iterative algorithm.
15.1 Background
The two-phase iterative algorithm of [27] consists of two phases that iterate until
either (i) an exact solution of the given problem instance is identified, or (ii) a pre-
specified number of subsequent iterations ` have taken place. Threshold ` is called
the limiting factor and must remain low enough to allow for a computationally effi-
cient solution. The first phase of the algorithm utilizes the inline algorithm to hide
the sensitive knowledge. If it succeeds, then the process is terminated and database
D is returned. This phase causes the retreat of the positive border of D
O
in the lat-
tice, thus excluding from F
D
the sensitive itemsets and their supersets. If the first
