Database Reference
In-Depth Information
sensitive rules. The algorithms in this class differ in the methodology they follow to
enforce the new, revised borders, in the sanitized database. The theory of border re-
vision is critical for the understanding of the border-based approaches and is exten-
sively covered in Chapter 9. Following that, Chapters 10 and 11 present two popular
border-based association rule hiding methodologies that have been proposed.
The third class of approaches contains non-heuristic algorithms which conceive
the hiding process as a constraints satisfaction problem (an optimization problem)
that they solve by using integer programming. The main difference of these ap-
proaches, when compared to those of the two previous classes, is the fact that the
sanitization process is capable of offering quality guarantees for the computed hid-
ing solution. The modeling of the hiding problem as an optimization problem en-
ables the algorithms of this category to identify optimal hiding solutions that mini-
mally distort the original database as well as introduce no side-effects to the hiding
process. Exact hiding approaches can be considered as the descendant of border-
based methodologies. They operate by first applying border revision to compute a
small portion of itemsets from the original database whose status (i.e., frequent vs.
infrequent) in the sanitized database plays a crucial role to the quality of the hid-
ing solution. Having computed those itemsets, the exact methodologies incorporate
unknowns to the original database and generate inequalities that control the status
of selected itemsets of the border. These inequalities along with an optimization
criterion that requires minimal modification of the original database to facilitate
sensitive knowledge hiding, formulate an optimization problem whose solution (if
exists) is guaranteed to lead to optimal hiding. It is important to mention that unlike
the two previous classes of approaches that operate in a heuristic manner, exact hid-
ing methodologies achieve to model the hiding problem in a way that allows them
to simultaneously hide all the sensitive knowledge as an atomic operation (from the
viewpoint of the hiding process). On the negative side, these approaches are usually
several orders of magnitude slower than the heuristic ones, especially due to the time
that is taken by the integer programming solver to solve the optimization problem.
