Research under NCGIA Research Initiative 2: Languages of
Spatial Relations
The broad aim of Research Initiative 2 has been to identify
elements of a fundamental theory of spatial relations. Initiative 2
chose natural language and mathematics as the principal media for
investigating and representing this problem; later initiatives
might approach the same objective through studies of vision, of
spatial behavior, or other topics.
One of the major advances during Initiative 2 was our
recognition of the importance of experiential realism, a
philosophical position advanced by George Lakoff and Mark Johnson,
based on the research of Eleanor Rosch and many others. The mental
models that people have of their worlds, and in our case especially
of geographic space, must be considered in efforts to build formal
or computational models of the world. But these mental models are
neither arbitrary nor idiosyncratic, because human bodies, minds,
and senses are all essentially similar. Cognitive linguists have
developed models of spatial concepts that are remarkably similar to
those used in cartography and GIS. Computational systems that deal
with geographic data must be able to support several models of the
same objects, and relate those models to each other, a result even
closer to the core of Initiative 3 ("Multiple Representations")
than to Initiative 2. The basic ideas of experiential realism and
its importance for formal models of geographic features have been
presented in papers at the Ninth International Symposium of
Computer-Assisted Cartography (Auto-Carto 9; Mark and Frank, 1989),
at a conference in Leicester, England on GIS Design Models (Frank,
in press), at the Association of American Geographers' meetings,
and in our chapter in the Longman's GIS book (Frank and Mark 1991)
and the introduction to the book reporting on the 1990 NATO
Advanced Study Institute (Mark and Frank, 1991), as well as in
several lectures at various universities and regional meetings.
Another outcome of Initiative 2 has had a more immediate impact
on the GIS community. This is the greatly-increased prominence of
user interface issues and human-computer interaction (HCI) in the
research agenda for geographic information and analysis. Although
some research on this topic was underway before the NCGIA was
established, Initiative 2 recognized the key relation of this topic
to cognitive science and human conceptualizations of space. The
concepts that people have about their worlds must be represented in
the user interface of the GIS; otherwise, users must perform
difficult translations between different conceptualizations of the
world. About a quarter of the Initiative 2 publications listed
below address the broad topic of user interfaces and query
languages, and this theme was developed into a new Research
Initiative, number 13, on "User Interfaces for GIS."
Our collaborative work on the topic began, in a sense, as we
wrote the original NCGIA proposal to NSF during 1987; however, the
period of concentrated effort and resources began with a Specialist
Meeting in January 1989. The formal resource period of Initiative 2
concluded with two international meetings in Europe during July
1990, but our work on the topic can be expected to continue
indefinitely. The remainder of this section describes research
projects in twelve topic areas within Initiative 2.
Algebras of Spaces and Morphisms between Spaces
During the I-2 Specialist Meeting, a conceptual framework for
spatial relationships was identified. Within this framework, there
is an algebra for each space describing its properties and
morphisms mapping from one space into another. Herring, Egenhofer,
and Frank (1990) have investigated this conceptual framework, and
one algebra has been defined with Egenhofer's theory of topological
relationships. The inclusion relation that defines a partial order
between spatial objects has been investigated as part of two master
theses (Greasley 1990, Perry 1990). It defines a particular aspect
of spatial relations that can be investigated with algebraic
methods.
Some spatial relationships exist in more than one algebra, and
we have investigated the mappings between the two spaces. John
Herring and others have shown in an example how mappings between
different algebraic description of space and properties of the
space can be defined (Herring et al. 1990). This contribution
introduced the notions of mathematical category theory as a method
of systematic discussion of algebras related by morphism.
Formal Definitions of Topological Relationships
In Egenhofer's dissertation, an approach to define binary
topological relationships has been proposed. This method is based
upon fundamental principles of algebraic topology using the four
intersections of the two boundaries and interiors and evaluating
them according to topological invariants such as the
emptiness/non-emptiness, dimension, or number of separations. An
article in the International Journal of Geographical Information
Systems lays out the fundamental mathematics and provides the
proofs for completeness for n-dimensional objects embedded in
n-dimensional space. Also, a joint paper with John Herring (an I-2
participant from Intergraph Corporation) was presented at the
Fourth International Symposium on Spatial Data Handling in Zurich.
These results have fostered a number of ongoing investigations
under Initiative 10, including the inference of new topological
information and reasoning over the combination of topological
relations, cardinal directions, and approximate distances. In
cooperation with Herring, Egenhofer has extended the theory to
apply to n-dimensional objects in m-dimensional spaces (m>=n).
Results were presented at AAG in San Diego and will be published in
a computer science journal.
Spatial Query Languages
Interactive query languages are the user's tools to request data
from a database. Conventional database query languages, such as
SQL, lack the particular functionality to address the retrieval and
representation of spatial data. In Egenhofer's Ph.D. thesis, a
comprehensive discussion of spatial query language components has
been presented. These are: the treatment of complex objects and
corresponding (geometric) operations; the graphical representation
of query results; interaction with graphically-displayed objects
via direct manipulation; the combination of multiple query results
in a single rendering; the description of the graphical
representation in terms of colors, patterns, and symbols; and the
definition of spatial context to be added to the user query asked.
An extension of SQL, including these spatial features as well as
the design of a human interface to such a spatial query language is
described and then compared with a comprehensive list of previously
proposed spatial query languages. The most important aspects of
this work have been published in Cartography and GIS and IEEE
Transactions on Data and Knowledge Engineering, and in refereed
conference proceedings as well as presented at professional
conferences.
Computational Models of Locative Expressions
One research theme at Buffalo has examined spatial prepositions and
other spatial-relational terms in a cross-linguistic framework.
This has had both theoretical and applied sides, and expects to
contribute to cognitive science as well as to GIA.
The theoretical side of this has been an examination of spatial
prepositions. Annette Herskovits analyzed the role of prepositions
in locative expressions in English, and identified about 35 basic
"use types" for the prepositions "in", "on", and "at" (Herskovits,
1987). The thrust of our Initiative 2 work on this has been to test
these use types in a cross-linguistic framework. A
cross-linguistically valid list of use types for spatial
prepositions (or equivalent grammatical elements) is essential to a
computational model of spatial relations. Work has concentrated in
particular on the relation involving lateral contiguity, as implied
in "Cleveland is on Lake Erie". Preliminary results have been
incorporated into a co-authored paper presented by Susan Haller in
Zurich (Haller and Mark 1990). During the summer of 1989, Haller, a
graduate student in Computer Science at Buffalo, conducted research
on computational models of locative expressions. Haller added the
generation of locative phrases in response to "where is" questions
in the CUBRICON Multi-Media Interface, a DARPA-supported project
monitored by the US Air Force. Haller's generation program chooses
a reference ('ground') object from among objects currently
displayed on a map, and also based on the discourse context as well
as the importance of various objects displayed. It then generates a
locative phrase relating the figure object to the ground object.
The contents of the locative phrase depend on the distance of the
figure to the ground and on the current scale of the map. Major
findings are summarized in Haller (1989), and Haller and Mark
(1990).
More recently, Eleanor Rosch's 'basic-level' concepts and radial
category structures have been applied to prepositions in English,
Spanish, French, and German. There appear to be central, basic
meanings of prepositions that often match up across languages. For
example, the same 'best example' situation, "on the table", shows
up for on (English), sur (French), sobre (Spanish) and auf
(German). In contrast, less central meanings (such as the relation
of passengers to buses) may vary more from language to language.
Results of this part of the research have not yet been
published.
In more practical terms, Matthew McGranaghan has studied the
translation of verbal description of locations, as they are
typically found on specimen labels in a herbarium, to a coordinate
based description of locations, that can be searched and displayed
with current GIS technology (McGranaghan, 1991). Systematic
biologists and museum collection managers are very interested in
such a capability and McGranaghan's continued work on the topic has
been supported by the National Science Foundation.
Driving Directions and Narrative Theory
A major thrust of the work at Buffalo has been to relate the
wayfinding directions to more general theories of narrative,
including how people understand stories, and how computer programs
can be designed to do the same. This may lead to procedures for
understanding the spatial aspects of stories in a more general
context, to computer integration of geographic texts into GIS, and
also could lead to improved verbal directions from vehicle
navigation-aid systems (see below). Researchers at Buffalo and
Santa Barbara have instituted a long-term study of informal driving
directions. Mark collected 31 sets of driving directions in the
United States (mostly in Buffalo) by approaching strangers in
public places, asking for directions to some other public places
(taping the response), and later transcribing them. In Valencia,
Spain, Gould collected 22 similar sets of directions (in Spanish).
Also, in Los Angeles, Sucharita Gopal collected sets of verbal
directions for walking to destinations on the UCLA campus. We have
found that the driving directions collected so far exhibit many of
the properties of stories and other forms of narrative, including
deixis, fictive motion, and metaphor. Also, there appear to be
substantial differences in directions produced by male and female
subjects, although further research will be needed to verify these
results and begin to account for them. Preliminary results were
presented in a session of four papers at the 1990 AAG meeting at
Toronto, in a paper presented in Zurich (Freundschuh et al. 1990),
and in a journal article (Mark and Gould, in press).
Acquisition and Representation of Spatial Knowledge
A major background theme contributing to the linguistic aspects of
spatial relations is the study of spatial knowledge acquisition.
Scott Freundschuh (Buffalo) continued his doctoral dissertation
research on models of spatial knowledge and on its acquisition.
This work was an out-growth of Freundschuh's masters thesis on
children's map-use and navigation abilities (Freundschuh 1990). He
has completed an experiment which explores how "regularity" of the
environment affects both the acquisition of spatial knowledge, and
the resulting accuracy of this knowledge in adults. Significant
differences can be attributed to geometric structure, and others to
whether knowledge was acquired from maps or from field experience.
Results appear to indicate that configurational knowledge is
acquired more effectively from maps than from experience, and more
accurately in a regular (gridded streets) environment than in an
irregular (curved streets, cul de sacs) environment. The Ph.D.
dissertation was successfully defended in October 1991, and results
will be published. Freundschuh is now an assistant professor at
Memorial University of Newfoundland, and has recently received a
research grant from the university to continue his research on
spatial knowledge acquisition.
In Maine, a particular problem regarding the representation of
detailed spatial data, especially the parcel data, has been under
study. Taher Buyong compared a representation that is based on
points with known coordinate values (the representation that is
traditionally used) with an alternative, where the relative
positions of points, as measured in the field, is the controlling
information. Different aspect of the concept, from the theoretical
bases in adjustment computation to the most practical and
economical factors, have been reported in several proceedings
papers and summarized in two journal articles. His Ph.D. thesis on
this topic has been completed.
Vehicle Navigation Aid Systems
One area of application for models of spatial knowledge and of the
production of spatial language is in the context of provision of
real-time navigation assistance for vehicle drivers. Three papers
on this topic, written by members of the Initiative 2 research
group at Buffalo, appeared in the proceedings of the IEEE-sponsored
Vehicle Navigation and Information Systems '89 conference in
Toronto, Ontario, September 1989, and were reprinted together as an
NCGIA Technical Report (Freundschuh, Gould, and Mark, 1989).
Earlier, Gould presented a paper on this topic at the AAG East
Lakes Division Meeting in Akron, Ohio, in October 1988; an expanded
and revised version of that paper subsequently has been published
in a regional geography journal (Gould, 1989b). Results of the
research on verbal directions for wayfinding will eventually be
applied to vehicle navigation aids.
A group of students at the University of Maine have investigated
the differences in spatial concepts to model a highway system,
depending on the task. They identified three distinct viewpoints,
namely the objects relevant for planning of a trip, the ones
relevant to give driving directions and the ones necessary for the
actual driving (Timpf et al. 1992). Timothy Nyerges of the
University of Washington has independently arrived at a very
similar breakdown into three tasks with their related
conceptualization, and reported on this at an NCGIA-organized
special session at the 1992 Annual Meeting of the Association of
American Geographers.
User Interfaces for GIS
An applied theme in the work at Buffalo was to examine the possible
role of cross-linguistic differences in spatial language with
regard to user interfaces. Initially, the study emphasized
Spanish-English differences. A paper on this work written by
Buffalo researchers was presented by Andrew Frank at the Second
Latin-American Conference on Geographic Information Systems, in
Merida, Venezuela, September 1989 (Mark, Gould, and Nunes, 1989).
That paper mixed a linguistic analysis of differences in locative
expression with a discussion of cross-linguistic and cross-cultural
issues in GIS user interfaces, and has been reprinted as an NCGIA
Report. Gould later received a National Science Foundation
Dissertation Improvement Grant to continue this research with
human-subjects testing in Barcelona (Spain) and Quito (Ecuador)
during 1990-91. Gould also organized a special session on user
interfaces for the GIS/LIS'89 meeting in Orlando, Florida, December
1989.
Our research on user interfaces led to the conclusion that the
spatial concepts applied by the user in understanding a task often
will differ from the spatial concepts used by the implementor of a
GIS, and this difference may cause major difficulties in the use of
GIS. Helen Couclelis presented a paper about a particular instance
of this problem, and the results were later published in a journal
article (Couclelis, 1991). And, as noted above, "User Interfaces
for GIS" was adopted as the 13th Research Initiative of the
NCGIA.
Metaphors for User Interfaces
People use different means to convey and perceive spatial
information than they use for non-spatial information. Traditional
'typed' query languages for user-machine interaction have been
shown to be cumbersome in a spatial environment where much data is
represented graphically. At Maine, Jeff Jackson (former graduate
student), Werner Kuhn, and Max Egenhofer investigated techniques
that are appropriate to communicate spatial information. These
investigations are based upon the methodologies for user interface
design developed in Egenhofer's and Kuhn's dissertations.
Jackson's master's thesis focused on the application of the pan
and zoom paradigm to view geographical and abstract information
spaces (see Jackson, 1990). He compared different solutions and
assessed them, looking for a close parallelism between the
conceptual and the actual operations on the user interface level.
He and Kuhn have presented their work at a Surveyor's and at a
Computer Science Conference. The major results have been a formal
definition of user interface metaphors and a new understanding of
pan and zoom operations, based on fundamental properties of human
vision. The method developed allows to compare interface designs
theoretically and eliminate candidate design that will likely
confuse users or will be hard to teach. Gary Volta, a graduate
student at Maine, has based his master's thesis on their work, and
applies the methods in an effort to find new ways of querying
non-spatial attributes.
Visualization of Spatial Information
Michael White (a former graduate student at Maine) worked with Kuhn
on the visualization and manipulation of spatial relations and
constraints. Kuhn continued this and investigated abstraction
mechanisms (classification, generalization and aggregation) as a
means to represent metrical relations (e.g. on distances, angles
and areas) graphically. This work is based on the Geometric
Constraint Calculus from Kuhn's dissertation. Kuhn presented papers
on this topic at the International Symposium on Spatial Data
Handling in Zurich, and at the American Association of Geographer's
meeting in Toronto.
Spatial Reasoning
Several research projects on spatial reasoning were identified as
part of the Initiative 2 research agenda, and begun under this
initiative. It concentrated on qualitative description of space and
concentrated on cardinal direction and approximate distances. In
particular, a special form of the reference frame problem (original
objective 2) was studied, and a formal, qualitative set of rules to
reason about cardinal directions, like 'North', 'South', etc.
(Frank, 1991) was developed. These rules were later combined with
reasoning about qualitative distances, like 'Far', 'Near', etc. The
results from this initiative led to a redefinition of the NCGIA
Research Initiative 10 "Spatio-Temporal Reasoning". First, the
initiative provided sufficient insight into spatial reasoning in
geographic space to outline a potentially worthwhile research
agenda. Second it provided evidence that spatial and temporal
reasoning in geographic space should be investigated jointly, as
they are closely related conceptually. A preliminary workshop to
explore the topic was held, and now an international conference to
be held in September 1992 in Pisa, Italy, is under preparation.
Other Activities
The major International Conference at the end of Initiative 2 was a
NATO Advanced Study Institute entitled "Cognitive and Linguistic
Aspects of Geographic Space", which was held in Las Navas del
Marques, Spain, July 8-20, 1990. The ASI received a grant of 2
million Belgian Francs (about $56,000) from NATO, and also had
partial support from the NCGIA. Mark was the Director of the ASI,
and Frank was the co-Director. A major product of the ASI was a
book, edited by Mark and Frank (1991). Another part of the
completion of Initiative 2 was the presentation of several papers
at the Fourth International Symposium on Spatial Data Handling in
Zurich.