Database Reference
In-Depth Information
Chapter 19
Summary
In this part of the topic, we studied the third class of association rule hiding ap-
proaches that involves methodologies which lead to superior hiding solutions when
compared to heuristic and border-based algorithms. The methodologies of this class
operate by (i) using the process of border revision (Chapter 9) to model the optimal
hiding solution, (ii) constructing a constraints satisfaction problem using the item-
sets of the computed revised borders, and (iii) solving the constraints satisfaction
problem by applying integer programming. Transforming the hiding problem to an
optimization problem guarantees the minimum amount of side-effects in the com-
puted hiding solution and offers minimal distortion of the original database to ac-
commodate sensitive knowledge hiding. Unlike the previous classes of approaches,
exact hiding algorithms perform the sanitization process by considering all relevant
data modifications to select the one that leads to an optimal hiding solution for the
problem at hand.
In Chapter 13, we surveyed Menon's algorithm [47], which is the first approach
to incorporate an exact part in the hiding process, effectively identifying the min-
imum number of transactions from the original database that have to be sanitized
for the hiding of the sensitive knowledge. Following that, in Chapters 14, 15 and
16 we presented three exact hiding methodologies that have been recently proposed
to compute optimal hiding solutions. The achieved optimality in the hiding solution
that is computed by the exact hiding algorithms comes at a cost to the computa-
tional complexity of the sanitization process. In Chapter 17, we elaborated on a
parallelization framework that was proposed in [26] to improve the scalability of
exact hiding algorithms. Through the use of this framework, the exact algorithms
can scale to large problem instances, provided that the necessary number of pro-
cessors are available. Last, in Chapter 18, we presented a layered approach to the
quantification of the privacy that is offered by the exact hiding methodologies. By
using this approach, the data owner can achieve the desired level of privacy in the
hiding of the sensitive itemsets at a minimal distortion of his or her data. Moreover,
he or she can decide the extent to which each sensitive itemset will be hidden in
the sanitized database by tuning the corresponding constraints in the CSP that is
produced by the exact hiding methodology.
