×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

Full text

Title
The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Author
Chen, Jun

ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
Copy (1)
Fig.6 Steps of spatio-temporal retrieval
4. SPATIOTEMPORAL RETRIEVALS
In GIS which deals with discrete temporal events, the types of
retrievals are categorized to the following:
(1) Spatial retrieval of the present data
(2) Spatial retrieval of a specified time data
(3) Detection of the difference between two specified times.
The first type of retrieval is not temporal retrieval. Conventional
GISes usually execute this type retrieval. The proposed data
structure can execute the retrieval by simply not using the
extension for temporal data, as described in [10]. There is no
retrieval time loss by the extension. In the following two
subsections, the other two types of retrievals are described.
4.1 Expansion of GBD-tree for temporal data
Basic idea how to manage spatio-temporal data is described in
[10]. The method uses geographic differential script file (GDSF) to
record past data. Then, this paper describes about abstract
feature of the data structure. The largest difference between the
original GBD-tree and the structure for spatio-temporal data is the
latter has a priority queue attached to every leaf node to store past
data.
GBD-tree uses different mechanisms when to register data and
retrieve data. The characteristic is very important when to insert
temporal data. The leaf node in which the temporal data is to be
inserted is determined depending on the center position of the
data. On the other hand, the node is not determined uniquely on
R-tree and its successors because the data are divided by the
shape of the MBR at the time that the division is invoked.
The priority of the queue is ordered by the time print from new to
old. To distinguish the MBR of temporal data from that of present
data, the MBR of the present data is denoted as MBRp, and the
MBR of the temporal data is denoted as MBRt.
Retrieval from the queue is also required in order to restore the
old timed data, In order to avoid omission of temporal data during
spatial retrieval, each node of the GBD tree has the MBR of
temporal data. When restoring the map of a specific date, spatial
retrieval is executed, referencing the MBR of temporal data
attached to each node. If the MBR of temporal data overlaps the
specified retrieval area and if the node is a leaf node, then the
queue storing temporal data is reviewed and applied to the
command that is controlling the current data set.
4.2 Spatial retrieval of specified time data
The most typical spatial retrieval is range retrieval. Other spatial
retrieval (for example, to find nearest neighbor) can also be
executed by a combination of range retrieval. The following
describes how to do range retrieval on the proposed data
structure.
First, retrieval of the present data is done by the usual method of
searching the GBD tree. Specifically, the overlap between the
specified retrieval area and the MBRp on each node is inspected.
If these two are overlapping, descend the tree and repeat the
same check for all the child nodes. If the node is a leaf node,
select the entities actually included in the specified range and add
the entities to the result set. In this searching process, there is no
overhead time caused by adding temporal information to the tree
structure.
When a particular time (old date) is specified outside of the
retrieval range, the priority queues attached to the leaf nodes are
inspected. Range retrieval of a specified time is executed by the
following steps, let the specified time be T and the specified range
be R.
(1) empty the result set S.
(2) check whether MBRp or MBRt overlaps with R
(3) if they are overlapping and the node is not a leaf node,
descend the tree and repeat the check for all child nodes.
(4) if they are overlapping and the node is a leaf node, copy the
data in the leaf node to a working space W.
(5) apply the GDSF commands attached to the node whose time
print is not older than T.
This operation is executed on the data in the working space W.
Add the result of W to S.
Fig.6 summarizes the steps of temporal retrieval. Every leaf node
consists of two parts, the present data and the historical data
queue. After having reached a leaf node, the present data part is
copied to a working space W. Then the GDSF commands are
applied until specified time. The contents in W are modified to the
states of the specified time. Finally, spatial retrieval is performed
on W.
The most important points of the method are in step 5. The first
point is that the range retrieval with specified time is executed on
a working space W, and there are no effects on the spatial data
stored in the GBD tree. The second is that the influence of the
operations by the GDSF commands is restricted within each leaf
node. For example, a command to insert an entity has no effect on
the other leaf nodes. When there is an insertion command on a
priority queue of a leaf node, execution of this command has no
effect on the results of the operation on the other nodes. In
addition, if there is a deletion command on a priority queue of a
leaf node, the object must exist on the same leaf node, because
the GBD tree distributes entities to individual leaf nodes according
to the center points. Also, deletion commands have no effect on
other leaf nodes.
4.3 Detection of the difference between two specified times
The comparison of two specified points in time is a frequently
requested operation in spatiotemporal GIS. The proposed data
structure can execute this type of operation easily.
Let two specified points in time be t1 and t2 (t1 < t2: t1 is older
than t2). This type of retrieval, the step (1) in Fig.6 is not
necessary, because the state of the present has no effect on the
result. Fist, skip the historical data queue until the time print is