Database Reference
In-Depth Information
(
x,y
) coordinates) or relative to a network, called
free
and
network-constrained
movement, respectively.
Structures proposed to index free movement include the STR-tree and the
TB-tree. Both are R-tree variants with the goal of keeping 3D line segments of
the same trajectory (units in the terminology of this chapter) clustered together
on pages. Whereas the STR-tree modifies the insertion and split strategy of the
R-tree toward this goal, the TB-tree does this in a more radical way and ensures
that a leaf page contains only segments of the same trajectory.
Besides such specialized structures, regular R-trees can also be used to index
the spatial, temporal, or spatio-temporal dimensions.
In network-constrained movement, the position of a moving object is
described relative to an edge of the network graph or a path in the network.
Two index structures for this case are the FNR-tree and the MON-tree.
Secondo includes implementations of the R-tree as well as of the TB-tree and
the MON-tree. In most applications, for example, the BerlinMOD benchmark
(see Section
3.8
), just R-trees are used. Generally, the index serves to retrieve
sets of candidates based on bounding box comparisons, which need to be further
checked for exact fulfillment of a query predicate. This is the so-called filter-
and-refine strategy.
When indexing moving points by R-trees, different granularities can be cho-
sen. The roughest one is to index the
mpoint
as a whole. If an
mpoint
was
observed over a long period, its bounding box may be very large, leading to a
lot of dead space within the index. The index will contain only a few entries, but
its selectivity is bad; this means the resulting candidate set will contain a lot of
false hits. The other extreme is to index single units of the
mpoint
. Here, com-
pared with indexing of the whole
mpoint
, less dead space is produced. But the
complete
mpoint
is distributed over many index entries. A third way is indexing
groups of connected units. All three possibilities are available in SECONDO.
3.6 Hermes
Another system dealing with moving objects is
Hermes
. It is implemented on top
of the Oracle 10g database system using PL/SQL as a programming language.
Beside the core system of Hermes, there is an implementation of a web-based
query builder and viewer. Hermes does not implement own data structures for
spatial objects, rather it uses the spatial objects of the underlying system.
Because Hermes implements the same data model as SECONDO does, the
data types and operations on them are quite similar. Additionally to the types
provided by SECONDO, Hermes has implementations for moving circles, moving
rectangles, and moving collections (sets of moving objects of different types).
Like SECONDO, Hermes uses the sliced representation for representing mov-
ing objects. Units belonging to a moving object are stored within a nested table.
