Database Reference
In-Depth Information
Table 14.5: The experimental results for the three datasets.
Dataset
Hiding
Scenario
u
nm
vars
Distance
BMS-1
HS1
157
128
BMS-1
HS2
359
301
BMS-1
HS3
60
19
BMS-1
HS4
120
12
BMS-1
HS5
120
8
BMS-1
HS6
228
21
BMS-1
HS7
150
24
BMS-2
HS1
12
3
BMS-2
HS2
36
18
BMS-2
HS3
24
3
BMS-2
HS4
40
8
BMS-2
HS5
40
4
BMS-2
HS6
80
12
Mushroom
HS1
32
8
Mushroom
HS2
68
20
Mushroom
HS3
64
12
Mushroom
HS4
128
16
Mushroom
HS5
128
8
Mushroom
HS6
256
24
Mushroom
HS7
160
16
14.3.3 Experimental Results
The inline algorithm was tested in the following hiding scenarios: hiding 1 1-itemset
(HS1), hiding 2 1-itemsets (HS2), hiding 1 2-itemset (HS3), hiding 2 2-itemsets
(HS4), hiding 1 4-itemset (HS5), hiding 2 4-itemsets (HS6), and hiding 1 5-itemset
(HS7).
Table 14.5
summarizes the attained experimental results. The number of u
nm
variables participating in the CSP provides an estimate of the worst-case scenario in
the context of the inline algorithm; it is equivalent to the maximum distance between
D
O
and D. The fourth column shows the actual distance of the two databases as
reported by the solver. It corresponds to the actual number of items that were hidden
from individual transactions of D
O
.
14.3.4 Discussion on the Efficiency of the Inline Algorithm
At a first glance, a serious shortcoming of the inline algorithm seems to be the time
that is required for solving the produced CSPs, especially due to the number of con-
straints introduced by the CDR approach. However, due to the fact that the produced
constraints involve binary variables and no products among these variables exist, it
turns out that the solution time (although certainly much higher than that of heuristic
approaches) remains acceptable. To support this claim, in [23] the authors created
