Databases Reference
In-Depth Information
many applications, valuable data cubes are outsourced to specialized parties
or provided for direct and interactive uses.
Guo et al. [9] proposed a robust watermarking scheme to protect the
owner's rights in data cube applications. The basic assumption is that all
watermarkable values in a data cube are numeric, and that small changes in a
small portion of these values are acceptable. For each cell in a data cube, the
owner of the data seeds a cryptographically secure pseudo-random sequence
generator
S
with a secret key
K
in concatenation with the cell's feature at-
tributes. If
S
1
mod
γ
= 0, then the cell is selected to embed a watermark
bit; otherwise it is ignored. Given
η
watermarkable cells, roughly
η/γ
cells are
selected. For each selected cell, a bit position among
ξ
least significant bits is
selected to embed a mark bit in the same way as in Agrawal and Kiernan's
scheme.
The most prevalent data cube operations are aggregation queries. To elim-
inate errors introduced by watermark to aggregation queries, a mini-cube is
constructed for each cell that is modified in watermark insertion. Suppose
that the value
d
(
X
i
,Y
j
,Z
k
) of cell at position (
X
i
,Y
j
,Z
k
) in a 3-dimensional
data cube is decremented by one in watermark insertion. Based on the posi-
tion of
d
(
X
i
,Y
j
,Z
k
), three other cell values
d
(
X
xc
,Y
j
,Z
k
),
d
(
X
i
,Y
yc
,Z
k
), and
d
(
X
i
,Y
j
,Z
zc
) are selected. The values of these cells are incremented by one
so as to balance the deviation in any 1-dimensional aggregation (i.e., aggre-
gation along one feature dimension) that involves cell (
X
i
,Y
j
,Z
k
). Similarly,
three more cell values
d
(
X
xc
,Y
j
,Z
zc
),
d
(
X
i
,Y
yc
,Z
zc
), and
d
(
X
xc
,Y
yc
,Z
k
)are
decremented by one, and one last cell value
d
(
X
xc
,Y
yc
,Z
zc
) is incremented by
one. These seven cells, which are called the balance cells, form a mini-cube to-
gether with the watermarked cell (
X
i
,Y
j
,Z
k
). With a mini-cube constructed,
any data cube aggregation that involves at least two cells in the mini-cube
remains unchanged after watermark insertion.
The mini-cube should be constructed such that: (i) the balance cells should
not be selected from any cell that is used in watermark insertion so as to avoid
interfering with the watermark insertion and detection; (ii) most aggregation
queries would involve at least two cells in the mini-cube; and (iii) the modifi-
cation to the balance cells should be minimal. Guo et al. [9] have shown that
this can be done effectively and eciently in real world applications even for
very large data cubes.
7.3 Streaming Data
A Robust Watermarking Scheme
Sion, Atallah, and Prabhakar [23] proposed a robust watermarking scheme
for streaming data. The scheme embeds a multi-bit watermark
wm
to an
infinite sequence of numerical data items
x
1
,x
2
,...
, which are normalized
in the interval (
0
.
5
,
0
.
5). The basic idea is to use some extreme values and
their neighboring values as watermark bit-carriers. An extreme value is a local
−
