Database Reference
In-Depth Information
forced to only contain segments belonging to the same trajectory, thus
making much larger concessions in MBR overlap. The insertion strategy
for the TB-tree is simply to find the previous segment of the trajectory
being inserted and place this segment in the same MBR. If this is not
possible, instead of splitting which would break apart segments from
the same trajectory, a new node is constructed for the segment and is
inserted in the first non-full parent. All of the leaf nodes containing a
trajectory are connected through a doubly-linked list so that an individ-
ual object can be retrieved from any individual segment.
As compared to a 3-dimensional R-tree, both the STR-tree and the
TB-tree result in more compact index structures with space utilization,
or how tightly packed the nodes of the index structure are, approach-
ing 100%. Additionally, both structure provide improved query times
for range queries over a small numbers of moving objects, however, as
the number of objects increased, the R-tree typically provided fewer
node accesses. However, for
combined queries
, which retrieve trajecto-
ries through various means, the TB-tree outperformed the STR-tree and
the R-tree by an order of magnitude even for a large number of mobile
objects.
Chakka et al. [11] introduce a scheme for indexing spatiotemporal
trajectories called
Scalable and Ecient Trajectory Index
(SETI). The
idea proposed by the authors is that splitting the space dimensions from
time, allows spatially close trajectory segments to be grouped together
and then
indexed by time, which provides a more compact and eciently
searchable structure. Their approach is to first statically partition the
space over which objects move and then maintain an index structure
only over the time intervals of segments contained within each disjoint
spatial partition. Each trajectory segment in a space partition is indexed
with an R-tree by a two dimensional point representing the start and
end time of that segment.
Queries are processed using a spatial and temporal filtering followed
by a refinement step to construct the answer set. The spatial filtering
simply returns all of the spatial partitions contained within the spatial
partitions that are contained within (or overlap with) the query region.
The subsequent temporal filtering simply poses a range query to the
R-tree in each spatial partition to retrieve the individual trajectory seg-
ments. A refinement step is necessary only over those spatial cells that
partially intersect with the query region.
This conceptually simple idea of splitting the time and space dimen-
sions was shown to provide significant improvements in query processing
time over TB-tree. Experimental results show that SETI consistently
provides lower query processing times for spatial range queries over time
