Databases Reference
In-Depth Information
presented next) is based on the maintenance of three disk arrays that keep
low coordinates of objects (i.e., x
1
, y
1
, and t
1
) separate in a sorted order.
3
Several queries involving spatiotemporal operators require the retrieval
of one array only, using divide-and-conquer techniques. Temporal layout
queries belong to this group. However, the majority of queries involves infor-
mation about more than one axis. Thus, the retrieval of more than one array
and the subsequent combination of the answer sets are necessary for such
cases. Efficient indexing mechanisms that could combine spatiotemporal
characteristics of objects to efficiently support a wide range of spatiotemporal
operators need to be present in an IMD authoring tool. The next subsections
propose two indexing schemes and their retrieval procedures.
A Simple Spatial and Temporal Indexing Scheme
A simple indexing scheme that could handle spatial and temporal character-
istics of media objects consists of two indexes:
A spatial (two-dimensional) index for spatial characteristics (the id
and the x
1
, x
2
, y
1
, y
2
values) of the objects;
·
A temporal index for temporal characteristics (the id and the t
1
, t
2
val-
ues) of the objects.
·
As an example, Figure 8.1 shows such an index based on the well-known
multidimensional indexing scheme of R-trees [12].
We argue that the adoption of this indexing scheme improves the
retrieval of spatiotemporal operators compared to the sorted-arrays scheme.
Even for complex operators where both tree indexes need to be accessed (e.g.,
for the overlap_during operator), the cost of the two indexes response times
is expected to be lower than the retrieval cost of the (three) arrays. A weak
point of the scheme already has been mentioned. The retrieval of objects
according to their spatiotemporal relationships (e.g., the overlap_during one)
with others demands access to both indexes and, in a second phase, the com-
putation of the intersection set between the two answer sets. Access to both
indexes is usually costly, and, in many cases, most of the elements of the two
answer sets are not found in the intersection set. In other words, most of the
disk accesses to each index separately are useless. A more efficient solution is
3.
Instead of using low coordinates, one can select high coordinates (or six arrays with low
and high coordinates). The decision does not affect the discussion that follows and its
conclusions.
