Database Reference
In-Depth Information
16.3.3 Formulation and Solution of the CSP
The CSP formulation that is adopted by the hybrid hiding algorithm is presented in
Fig. 16.1,
while
Fig. 16.2
demonstrates the CDR approach that is applied to elim-
inate any products of binary variables in the considered constraints. Assuming that
D
X
is large enough, and that D
O
allows for an exact solution, the above hiding
formulation is capable of identifying it. However, D
O
may not always allow for
an exact solution. Section 16.3.5 presents an approach used in [26] for dealing with
suboptimality, while the following section examines the issue of validity in the trans-
actions of D
X
and presents an algorithm for removing unnecessary transactions.
Replace
All
å
T
q
2D
X
Y
s
S
thr;Y
s
=
Õ
i
m
2T
q
u
qm
With
8
<
:
c
1
: Y
s
u
q1
c
2
: Y
s
u
q2
.
c
Z
: Y
s
u
qm
Y
s
u
q1
+u
q2
+: : :+u
qm
jZj+1
8i
And
å
s
Y
s
S
thr
where Y
s
2f0; 1g
Fig. 16.2: The Constraints Degree Reduction approach.
16.3.4 Minimum Extension and Validity of Transactions
The incorporation of the safety margin threshold in the hiding process may lead to
an unnecessary extension of D
X
. Fortunately, as discussed in [26], it is possible to
identify and remove the extra portion of D
X
that is not needed, thus minimize the
size of database D to the necessary limit. To achieve that, one needs to rely on the
notion of null transactions, appearing in database D
X
.
Definition 16.5. (Null transaction) A transaction T
q
is defined as null or empty if
it does not support any valid itemset in the lattice. Null transactions do not support
any pattern from Pnf?g.
