Database Reference
In-Depth Information
Chapter 14
Inline Algorithm
In this chapter, we present in detail the first algorithm that has been proposed which
does not rely on any heuristics to secure the sensitive knowledge derived by asso-
ciation rule mining. Similarly to Menon's algorithm (covered in Chapter 13), the
inline algorithm of [23] aims to hide the sensitive frequent itemsets of the original
database D
O
that can lead to the production of sensitive association rules. As a first
step, we will introduce the notion of distance between two databases along with a
measure for quantifying it. The quantification of distance provides us with important
knowledge regarding the minimum data modification that is necessary to be induced
to the original database to facilitate the hiding of the sensitive itemsets, while min-
imally affecting the nonsensitive ones. By trying to minimize the distance between
the original database and its sanitized counterpart, the inline algorithm formulates
the hiding process as an optimization problem in which distance is the optimization
criterion. Specifically, the hiding process is modeled as a CSP which is subsequently
solved by using a technique called Binary Integer Programming (BIP). The attained
solution is such that the distance measure is minimized. It is important to mention
that since the inline algorithm is non-heuristic, it does not suffer from local minima
issues that would lead the hiding algorithm to suboptimal (i.e., locally — but not
globally — best) solutions. As an effect, this methodology is guaranteed to identify
hiding solutions of superior quality when compared to state-of-the-art heuristics and
border-based approaches.
The remainder of this chapter is organized as follows. Section 14.1 introduces the
privacy model that is employed by the inline algorithm for the identification of exact
and optimal hiding solutions. Next, in Section 14.2, we demonstrate the solution
methodology that is adopted. Finally, Section 14.3 presents some experiments that
demonstrate the effectiveness of the approach towards solving the problem. More
experiments comparing the inline algorithm to other state-of-the-art approaches are
included in Chapters 15 and 16.
