Databases Reference
In-Depth Information
directly into the tree. After the structural change, the TPR of the parent
node may need to be updated accordingly and the described process may
be repeated up to the root node. If the root node is time-split at time
t
,a
pointer to the new alive node together with timestamp [
t
,
ā
) is added to
a special root array that is stored in the main memory [10].
Note that if the tree is constructed at
t
0
and time split for the alive root
element of the root array occurs at
, each root element in
the root array is associated with time interval [
t
0
,t
1
)
,
[
t
1
,t
2
)
,...,
[
t
nā
1
,t
n
)
,
and [
t
n
,
{
t
1
,t
2
,...,t
n
}
). The associated time interval for each root element represents
the ephemeral structure of the tree during those time intervals. Thus, if
we want to know the status of the tree at time
t
, we simply need to find
arootelement
r
from the root array
R
such that the time interval of
r
includes
t
.
ā
Observe that there are two kinds of moving objects: one is currently mov-
ing objects so that their ending location is predicted but not decided (called
alive moving objects), and another type is the objects that already stopped
moving, or changes its velocity or anticipated future location above the prede-
fined deviation level (called dead moving objects). During update (insertion or
deletion) of moving objects in the tree, the leaf node where the update occurs
are evaluated to see if there still exists a pre-specified range of alive moving
objects. If the number is out of this specified range, alive objects in the node
are copied into a new node (called time split). The original node is used for
evaluating the past positions of moving objects; the newly created node is for
the present and future positions of moving objects such as
S
TPR-tree. The
similar process is applied to index nodes: in this case, the number of alive
children nodes is checked if it is within the predefined range.
Because S
PPF
-tree maintains past positions of moving objects as well, the
overlaying process is more complicated than that of the
S
TPR-tree because
authorizations are required to be maintained properly not only for present
and future positions but also past positions: in case of
S
TPR-tree, the tree is
re-constructed after some reasonable duration of time, and authorizations are
batch-overlaid on the tree. Thus, there is no need to deal with maintenance
of authorizations during the tree's life time. Since the S
PPF
-tree handles all
the history information as well, it is necessary to maintain the overlaid au-
thorizations more carefully in order not to violate the overlaying strategy. An
authorization log is introduced to handle this situation: whenever an autho-
rization is applicable to the tree, the authorization log overlays the newly
applicable authorization on the alive nodes, and relocate the authorizations
from the alive nodes to the dead nodes if they are only applicable to the dead
nodes. An authorization log is a data structure constructed by spreading all
the authorizations on the time line. As time elapses, a new authorization
becomes applicable to the tree when the valid time duration of the authoriza-
tions is overlapped with the tree's valid time duration, i.e. between current
time and the time horizon. Then, the authorization log triggers an auth begin
