ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001
A SPATIO-TEMPORAL GEOGRAPHIC INFORMATION SYSTEM BASED ON
IMPLICIT TOPOLOGY DESCRIPTION: STIMS
Yutaka OHSAWA 1 Atushi NAGASHIMA 2
1 Department of Information and Computer Sciences, Saitama University
Shimo-okubo, 255, Urawa, Saitama, 338-8570, Japan
Tel: 81-48-858-3717, Fax: 81-48-858-3716
E-mail: ohsawa@mm.ics.saitama-u.ac.jp
2 Graduate School of Science and Engineering, Saitama University
Shimo-okubo, 255, Urawa, Saitama, 338-8570, Japan
Tel: 81-48-858-3717, Fax: 81-48-858-3716
E-mail: nagashi@mm.ics.saitama-u.ac.jp
KEYWORDS Implicit Topology Description, Spatio-temporal Data Management, Free GIS
ABSTRACT
This paper proposes a novel geographic information system named STIMS (Spatio-temporal Information Management System). The most
significant characteristic feature of the system is on the point that the system based on an implicit topology description method. This
system does not have topological information, for example administrative borderlines and transportation networks, explicitly, but implicitly.
The system restores the topological information by spatial operations. By this implicit topology description, Spatio-temporal retrieval
becomes easily, and spatial operations over the data sets gathered through computer network can be done easily. The authors are now
implementing a Spatio-temporal geographic information system based on the concept. This paper describes the concept and an
implementation.
1. INTRODUCTION
On conventional geographic information systems, topological
information has been described explicitly using relational tables or
pointers [1]. The early days when GIS came into existence
(1970s), the computer processing speed was very slow and the
amount of main memory was limited. Then, to express topological
information explicitly was mandatory for obtaining good response.
During later two or three decades, computing speed has
increased more than 1,000 times. By this computing power
progress, new methodology which restore the topological
information by calculation when it is necessary becomes
actual[2],[3]. We call this methodology as implicit topology
description method.
When we want to know the shortest path between two specified
points (start and destination) over a road network, the path can be
found by successive following the connected road segments
under the control of A* algorithm[4] or Dijkstra algorithm[5]. When
the topological information of road network is given explicitly, the
set of connected road segments at an intersection can be known
very easily by following pointers or inquiring relational tables. On
the other hand, on implicit topology model, the topological
information is restored by spatial retrieval at the each intersection.
The connecting road segments at an intersection have the same
end point, then these road segments can be found by a spatial
search to find the road segments whose one of the end point meet
the intersection location. This type of spatial retrieval can be done
efficiently using spatial data structure, for example R-tree(6] or its
descendants[7]. In STIMS, GBD-tree[8],[9], which developed the
same purpose, is used for this spatial search.
By possessing topological information implicitly, temporal
information management becomes easy[10]. For example,
suppose the situation to manage the transition of administrative
borderline for 50 years time span. During the time span, cities
may have been merged and split, and the name of the cities may
have been changed. When explicit topological expression is used
for managing these changes, the structure becomes very
complicated like spaghetti. On the other hand, on implicit topology
description model, the data structure stays very simple despite
such changes. Because, city border at specified time is restored
by spatial retrieval using Spatio-temporal key.
We implemented the system on PC by C++. By our experimental
results, retrieval of the connected line segments at a specified
node can be done 70-nanosecond, and restoration of the shape
of city block can be done 1 to 2 microseconds on PCs. The
computing speed is enough for interactive use of GIS. However,
such retrieval time is little slower in comparing with conventional
explicit topology GIS. Then, we developed a cache technique[11]
for restored topological information. The cache keeps restored
topological information until the cache size limit, then reused them
for further requests. Using this, the calculation time reduced to
one-tenth.
In section 2, data model used in STIMS is described. In section 3,
several spatial operations to restore topological information is
described. In section 4, temporal data handling method and its
data structure is described. GIS refers several dataset, including
spatial entity file, attribute data file, several definitions and
legends. Such kinds of data formats are described in section 5.
Section 6 concludes the paper.
2. STIMS DATA MODEL
Geographic entities dealt in this paper are limited in
two-dimensional space for simplicity of description. Geographical
entities dealt in a two-dimensional GIS can be categorized into
three classes, points, lines and regions, depending on their
geometrical feature. For example, macroscopically, buildings can
be dealt as points, roads and power supply network can be dealt
as a set of lines. Administrative districts are regions. Here we
describe how such data is considered in the implicit topology
model.
Fig.l Network node and links
Figure 1 shows part of a network, such as road network. In this
figure, three roads, L-1, L-2 and L-3 are connected each other at
node N. In the network, roads correspond to links and the
intersections correspond to nodes. The explicit topology model,
which has been used usual GIS, deals with the topology of the
network explicitly using pointers or relation tables.
The implicit topology model, on the other hand, describe
topological information by definition and method functions. This
method restores the topological relation through spatial
operations. Namely, other links connected to the specified link are
