Database Reference
In-Depth Information
Chapter 11
Max-Min Algorithms
Moustakides & Verykios in [50, 51] propose two border based methodologies that
rely on the max-min criterion for the hiding of the sensitive itemsets. Both method-
ologies use the revised positive border of the frequent itemsets to track the impact of
each tentative item modification that helps towards the hiding of a sensitive itemset.
Then, they select to apply those item modifications to the original database that ef-
fectively conceal all the sensitive knowledge, while minimally affecting the itemsets
of the revised positive border and, consequently, the nonsensitive frequent itemsets.
For each item of a sensitive itemset, the Max-Min algorithms identify the set of
itemsets from the revised positive border which depend on it, and select among
them the ones that are supported the least. Then, from among all minimum sup-
ported border itemsets (coming from the previously computed sets for the different
items of the sensitive itemset), the itemset with the highest support is selected as it is
the one with the maximum distance from the borderline that separates the frequent
from the infrequent itemsets. This itemset, henceforth called the max-min itemset,
determines the item through which the hiding of the corresponding sensitive itemset
will take place. The proposed Max-Min algorithms delete this item from selected
transactions in a way that the support of the max-min itemset is minimally affected.
When hiding multiple sensitive itemsets, the algorithms perform the sanitization in
a one-by-one fashion starting from the sensitive itemsets that have lower supports
and moving towards itemsets of higher support. Through experimental evaluation,
both methodologies are shown to provide superior hiding solutions when compared
to the BBA algorithm of [66, 67], while also being less computationally demanding.
In the rest of this chapter, we explain the main ideas behind the max-min opti-
mization criterion that is employed by the Max-Min algorithms to effectively con-
ceal the sensitive knowledge. Moreover, we shed light on the workings of the two
algorithms, as well as elaborate on their commonalities and differences. Specifi-
cally, in Section 11.1 we straighten out the underlying principles of the max-min
criterion and discuss the process that is followed by both algorithms for the hiding
of a sensitive itemset. Following that, in Section 11.2 we clarify the order in which
the Max-Min algorithms process the sensitive itemsets to effectively hide them in
the sanitized database. Last, Sections 11.3 and 11.4 present the different steps that
