Inline Algorithm - Association Rule Hiding for Data Mining - page 65

Fig. 14.1: The architectural layout for the inline approach.
remain frequent in D and therefore they should satisfy inequality (14.3). On the
contrary, all frequent itemsets in S max should be hidden in D and therefore they
must satisfy inequality (14.4). If at least one inequality does not hold for an itemset
in F 0 D , then the identified solution is non-exact but approximate.
An important observation that was made in [23] is that the two types of inequali-
ties, namely (14.3) and (14.4), are actually not of the same importance. Specifically,
while it is crucial to ensure that inequality (14.4) holds for all sensitive itemsets in
D, such that they are properly hidden, inequality (14.3) just facilitates the minimiza-
tion of side-effects in the hiding process. As we present in the following section, the
inline algorithm considers the difference in the significance of these two types of
inequalities in order to compute the best approximate solutions, when optimal ones
cannot be found for the problem at hand.
14.2 Solution Methodology
As is proven in [23] the NP-hard problem of the 2 M 1 inequalities can be reduced
to an extent that is solvable while yielding the exact same set of solutions. In what
follows, we discuss how this reduction is possible. Then, we demonstrate that based
on the reduced set of produced inequalities the hiding process in the case of the
inline algorithm can be formulated as a CSP that is solved by using BIP. The archi-
tectural layout of the inline algorithm is presented on Fig. 14.1.
14.2.1 Problem Size Minimization
Although the entire problem of the 2 M 1 constraints cannot be solved due to its
exponential growth, the authors of [23] demonstrate that it is possible to minimize
the number of inequalities that participate to the CSP, without any loss in the quality
of the attained solution. Specifically, certain inequalities of the system (referring to
the status of itemsets in D) can be removed from the CSP of the 2 M 1 inequal-
ities, without affecting its set of solutions. The rational behind this claim is that