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