Databases Reference
In-Depth Information
The first operation can be performed using the steps used for MSR, and the
second operation can be performed using the steps for SMR.
One main limitation of
S
TPR-tree is that it can only support the se-
curity/privacy policies based on the current and future locations of moving
objects, but not on the past locations. As a result, it cannot support the
security/privacy policies based on
track
privilege because the past status of
moving objects is not being stored. The S
PPF
-tree, presented next, eliminates
this limitation using the concept of partial persistence.
5.2 S
PPF
-Tree
The previously introduced
S
TPR-tree cannot support the security/privacy
policies based on tracking of mobile users. It is important to note that tracking
information could also be sensitive and therefore security policies are often
specified to reflect this. To eciently enforce these policies, the tree must
support this functionality in the sense that all the location history of moving
objects are preserved. S
PPF
-tree, an extension of
S
TPR-tree, can maintain
past, present and future positions of moving objects along with authorizations,
by employing partial persistent storage. S
PPF
is a variant of R
PPF
-tree [10],
which applies the concept of the partial persistence to the TPR-tree in order
to preserve the past locations of moving objects, as well. Partial persistence
is based on the following important concepts.
•
Evolution of Index Nodes and Data Entry:
In order to be trans-
formed to a partially persistent structure, each index (leaf or non-leaf)
node and data entry (moving objects) include two additional fields for
maintaining the evolution of the index records:
insertion time
and
dele-
tion time
. These are denoted as
N.insertionT ime
and
N.deletionTime
for
node
N
. If a new moving object is available and captured at time
t
0
, its
insertion time is set to
t
0
and deletion time is set to
. When the object
is logically deleted from the index at time
t
d
, its deletion time is changed
from
∞
to
t
d
. The same rule applies to index nodes. A node or a data
entry is said to be
dead
if its deletion time is less than
∞
∞
, otherwise it is
said to be
alive
.
•
Time Split:
When an update (insertion or deletion) occurs at a node
N
,
it may result in structural changes if it becomes underfull or overfull. If
this is the case, a
time-split
occurs to
N
. The time-split on a leaf node
N
at time
t
is performed by copying all alive entries in
N
at
t
to a new
leaf node
L
and timestamp of both
L
and those copied entries are set to
[
t
,
). In addition, the deletion time of
N
is set to
t
and
N
is considered
dead. Then, the new node
L
is investigated further in order to incorporate
it into the tree. Essentially, three different cases may arise: (1) split: If
L
is overfull, split it into two nodes and then insert these two nodes into
the tree. (2) merge: If
L
is underfull, accommodate by merging it with
another node. (3) no change: If
L
is neither overfull nor underfull, insert it
∞
