Database Reference
In-Depth Information
Fig. 3.2: The three classes of association rule hiding algorithms.
other hand, rely on formulating the association rule hiding problem in such a way
that a solution can be found that satisfies all the goals. Of course there is a possibil-
ity that an exact approach fails to give a solution, and for this reason, some of the
goals may need to be relaxed. However, this relaxation process is still part of the
exact approach, which makes it radically different from the heuristic approaches.
Moreover, the data owner has control over the side-effects that are introduced to the
database due to the the approximation strategy that is applied.
3.2 Classes of Association Rule Hiding Algorithms
Association rule hiding algorithms can be divided into three classes, namely heuris-
tic approaches, border-based approaches and exact approaches. The first class of
approaches involves efficient, fast algorithms that selectively sanitize a set of trans-
actions from the original database to hide the sensitive association rules. Due to their
efficiency and scalability, heuristic approaches have been the focus of attention for
the majority of researchers in the data mining area. However, there are several cir-
cumstances in which these algorithms suffer from undesirable side-effects that lead
them to identify approximate hiding solutions. This is due to fact that heuristics
always aim at taking locally best decisions with respect to the hiding of the sensi-
tive knowledge which, however, are not necessarily also globally best. As a result,
heuristics fail to provide guarantees with respect to the quality of the identified hid-
ing solution. Some of the most interesting heuristic methodologies for association
rule hiding are presented in the next part of the topic.
The second class of approaches considers association rule hiding through the
modification of the borders in the lattice of the frequent and the infrequent itemsets
of the original database. Borders [46] capture those itemsets of a lattice that con-
trol the position of the borderline separating the frequent itemsets from their infre-
quent counterparts. Data modification, applied to the original database to facilitate
sensitive knowledge hiding, has an immediate effect on the support of the various
itemsets and, subsequently, on the borders of the sanitized database. Border-based
algorithms achieve to hide the sensitive association rules by tracking the border of
the nonsensitive frequent itemsets and greedily applying the data modifications that
have minimal impact on the quality of the border to accommodate the hiding of the
