Database Reference
In-Depth Information
such as
speed
and
heading
. For example, it may be interesting to iden-
tify an object's top speed over a time interval, or find the set of objects
with a particular heading at a specified time. Combining topological and
navigational queries provide a powerful approach for analyzing complex
spatiotemporal patterns.
To eciently answer topological queries over trajectories, Pfoser et
al. [66] introduce two index structures, the spatiotemporal R-tree (STR-
tree) and the trajectory bundle tree (TB-tree). both structures naturally
extend the basic R-tree [28] to handle trajectories in a more ecient
manner. The problem with directly applying the R-tree to index tra-
jectories is the amount of
dead space
typically incurred. To maintain a
nearly
O
(
logN
) access time, whole trajectories must be stored as single
units; this reduces the discriminative power of the index structure due to
the large area necessary to bound such a region. Alternatively, splitting
each trajectory into a set of line segments improves the discrimination
of each bounding box, however, access time is now dependent on the
length of each trajectory (i.e. access time
O
(
klogN
)).
The approach utilized in the STR-tree is to segment trajectories while
keeping parts of the same trajectory close within the index structure to
improve the eciency of queries over large time intervals. As compared
to the R-tree, the major contributions of this index are new
insertion
and
split
methods which provide different optimization criteria. The authors
assume that each trajectory is associated with a unique identifier and
has already been partitioned so the index may already contain a partial
trajectory for an object. The insertion algorithm first attempts to fit the
new segment in the same minimum bounding box (MBR) as the previous
segment from the same trajectory. We may split this index node if it is
full as long as the parent is not full. Otherwise, the trajectory segment is
inserted using the original
ChooseLeaf
algorithm, which locates the leaf
node for which inserting the current segment will incur the lowest cost in
terms of MBR overlap, area and dead space [28]. The split algorithm also
considers how pairs of trajectory segments are related when optimizing
the split. Segments that are not related to any other segments in the
node (i.e. they come from different objects), may be placed into the new
node, otherwise, if all segments are related the node is partitioned by
time such that the newest segments will remain together. In general,
the insert and split procedures first optimize for trajectory preservation
(i.e. keeping segments of the same object nearby in the index structure)
and then for spatial closeness (i.e. minimizing the increase in an MBR).
In contrast to the STR-tree, the TB-tree takes a more dramatic ap-
proach and groups segments of the trajectory to
ensure
that they are
all 'bundled' together for fast retrieval. The leaf nodes of a TB-tree are
