Databases Reference
In-Depth Information
Authentication cost:
The embedded trees work exactly like MB-trees for point queries. Hence, each
embedded tree returns (
f
k
−
1)
d
k
hashes. Similarly to the MB-tree the total
size of the
VO
is:
e
=
N
R
·|
|VO|
r
|
+
|
s
|
+
d
q
−
2
d
m
−
1
m
+
m
+
2
|VO|
|VO|
(
f
k
−
1)
d
k
|
h
|
,
(17)
0
d
q
m
is the cost of a range query on the embedded trees of the bound-
ary nodes contained in the query sub-tree given by equation (11), with a query
range that covers all pointers to children that cover the query result-set.
The verification cost is:
where
|VO|
d
q
−
1
e
f
e
·C
k
+(
d
e
−
C
v
=
N
R
·C
H
|r|
+
d
q
)
·C
k
+
C
V
|h|
,
(18)
i
=0
where
C
k
=
N
i
·C
H
f
k
|h|
is the cost for constructing the concatenated hash of
each node using the embedded tree.
For
f
k
= 2 the authentication cost becomes equal to a Merkle hash tree,
which has the minimal
f
e
the
embedded tree consists of only one node which can actually be discarded,
hence the authentication cost becomes equal to that of an MB-tree, which
has larger
VO
size but higher verification time. For
f
k
≥
size but smaller verification cost. Notice that, as
f
k
becomes
smaller,
f
e
becomes smaller as well. This has an impact on
VO
construction
cost and size, since with smaller fanout the height of the EMB-tree increases.
Nevertheless, since there is only a logarithmic dependence on
f
e
versus a
linear dependence on
f
k
, it is expected that with smaller
f
k
the authentication
related operations will become faster.
VO
4 Authentication Index Structures in Dynamic Settings
In this section we analyze the performance of all approaches given dynamic
updates between the owner and the servers. In particular we assume that
either insertions or deletions can occur to the database, for simplicity. The
performance of updates in the worst case can be considered as the cost of a
deletion followed by an insertion. There are two contributing factors for the
update cost: computation cost such as creating new signatures and computing
hashes, and I/O cost.
Aggregated Signatures with B
+
-trees
Suppose that a single database record
r
i
is inserted in or deleted from the
database. Assuming that in the sorted order of attribute
A
the left neighbor
