RIA: Formalization, Inference, and Query Processing of Spatial Relations in Geographic Space

Max J. Egenhofer

National Center for Geographic Information and Analysis
Department of Spatial Information Science and Engineering
Department of Computer Science

Contact Information

Boardman Hall
University of Maine
Orono, ME 04469-5711
Phone: (207) 581-2114
Fax : (207) 581-2206
Email: max@spatial.maine.edu

WWW PAGE

http://www.spatial.maine.edu/~max/NSF-RIA.html

Keywords

spatial database systems, geographic information systems, spatial reasoning, spatial query languages, spatial query processing.

Project Award Information

Project Summary

Scientists and engineers using geographic databases need query languages with powerful spatial selection methods and capabilities to infer spatial information in a manner similar to a human expert. Crucial for geographic databases, containing very large amounts of spatial data, are appropriate operators to access and manipulate spatial data in large-scale, geographic space, far beyond what is currently being offered by traditional database management systems. The objective of the investigations was to construct a coherent reasoning system that integrates spatial concepts about topology, cardinal directions, and approximate distances so that they can serve as a spatial extension to geographic databases and query languages. The reasoning system focused on large-scale, geographic space. The hypothesis was that powerful and complex spatial reasoning can be formalized as the product of the interaction between relatively simple spatial relations with specific inference rules. First, individual spatial relations of topology, distance, and direction were formalized. Afterwards these formalizations were used to develop an integrated, comprehensive system, i.e., a more complex algebra, from the previously defined ones, adding more power through the coexistence of the different relationships in a single system. The major results are a set of primitives, with rules describing their combinations, for the design of domain specific spatial query languages.

Goals, Objectives, and Targeted Activities

These results provided an invaluable foundation for new work:

1. We learnt about the interdependencies of spatial relations and their inferences. Any comprehensive spatial algebra must address the semantics of these combinations, since they may provide important insights and inferences that are otherwise not available.

2. Through complementary work with an empirical scientist we identified the connections as well as missing gaps between some of the formalisms developed and people's usage of the corresponding spatial concepts in different natural languages. Future work in spatial data models need a close integration of the development of formalisms and their evaluations with human subjects in order to assess the usefulness of the results.

3. The methods employed under our earlier work was strongly geometry-based and, therefore, led immediately to implementable operators and data structures within the context of the current, geometry-based geographic information systems. Our work, however, focused primarily on the dominance of topology over directional and metric spatial information. Future work with a fresh approach and a new perspective is necessary with a cognitive, rather than a geometric motivation and starting point.

Indication of Success

The major result of work performed under grant IRI-9309230 is the theory for a qualitative spatial reasoning system. Our formalizations include a comprehensive model for binary topological relations among such spatial objects as regions, lines, and points, called the 9-intersection. The model has multiple levels of resolution such that, if necessary, more detail can be provided. At the level of greatest detail, the model describes when two topological relations are isomorphic. The model has been extended to deal with more complex spatial objects such as regions with holes, regions with separations, and heterogeneous objects such as entire river networks with lakes. The 9-intersection model is widely used by researchers who are studying spatial relations, as indicated by the many applications reported in the literature that build upon it. For example, almost half of the papers in the proceedings of the Sixth International Symposium on Spatial Data Handling (SSD '94) and the Second Conference on Spatial Information Theory (COSIT '95) refer to this work. More recently, the 9-intersection has become an area of study in database theory. Over the last few years, at least seven Ph.D. theses have focused on various extensions and applications of the 9-intersection with several others in progress. Industry adopted this model as a basis for implementations of spatial operators in Microstation Analysis, a commercial GIS, and in Oracle MD, a spatial extension of a relational DBMS. It was also incorporated into SAIF, the Spatial Archive and Interchange Format, and into the committee draft of the upcoming standards ISO TC 211 and SQL/Multimedia.

Project Impact

The grant directly supported two graduate students, with complementary funding for graduate research assistants by a University of Maine Graduate Research Assistantship. Jayant Sharma completed his Ph.D. in Fall 1995 on "Integrated Spatial Reasoning in Geographic Information Systems: Combining Topology and Direction." Nancy Selvaggio graduated in May 1996 with a Master's. Furthermore, Jung-Hong Hong worked on one task of the grant and completed his Ph.D. in 1994. Sharma and Hong have published their results in two journal articles and several refereed and non-refined conference proceedings.

The REU supplement supported John Florence during Summer 1994 and Chika Ukabam during Fall 1997. Florence investigated the distribution of spatial relations in various data sets. Stimulated by this research, Florence continued his education towards a master's degree and graduates in Summer 1997 with a Master's in Spatial Information Science and Engineering. His master's thesis is an outgrowth of the work done under the REU. He published two papers in conference proceedings. Ukabam is a second-year undergraduate. She participated in the design of a web-based user interface for a qualitative spatial reasoning system. Based on her research experience, she transferred her major from geology to spatial information engineering and continues to be involved in other early-career research activities.

The National Center for Geographic Information and Analysis (NCGIA)-a research consortium of comprising the University of California, Santa Barbara; the University at Buffalo; and the University of Maine-and the Department of Spatial Information Science and Engineering at the University of Maine. The NCGIA is a member of the Open GIS Consortium. The Department of Spatial Information Science and Engineering is a Center of Excellence in Land Information Studies and also part of a NASA Center for Excellence in Remote Sensing Applications. The University of Maine is a founding member of the University Consortium for Geographic Information Science (UCGIS) and recently was named an honorary and founding member of the Oracle Spatial Research Laboratory. Beyond the campus, NCGIA has excellent ties to the local GIS industry including the Sewall Company, Geo-graphics, and Vision International.

What activities have been enabled/spawned because of the accomplishments made possible by your award?

The RIA was a career boost for the PI. Since the start of this NSF project, the PI has built a strong research group focusing on geographic databases, spatial reasoning, and GIS user interface design. Currently, the group includes two research faculty (Dr. Anthony Stefanidis and Dr. Douglas Flewelling), and eight graduate research assistants, six of them being Ph.D. candidates, and regularly visiting national and international scientists. Over the past three years, the PI obtained funding from the National Science Foundation, the National Imagery and Mapping Agency, Advanced Research and Development Committee of the Community Management Staff, Rome Laboratory, DARPA (through a subcontract from TASC), the Scientific and Environmental Affairs Division of the North Atlantic Treaty Organization, Intergraph Corporation, Environmental Systems Research Institute, Space Imaging, and the Maine Mathematics and Science Alliance.

Project References

T. Bruns and M. Egenhofer (1996) Similarity of Spatial Scenes, Seventh International Symposium on Spatial Data Handling, Delft, The Netherlands, pp. 173-184, Taylor & Francis, London.

 E. Clementini, J. Sharma, and M. Egenhofer (1994) Modeling Topological Spatial Relations: Strategies for Query Processing, Computers and Graphics, 18(6): 815-822.

M. Egenhofer (1994) Deriving the Composition of Binary Topological Relations. Journal of Visual Languages and Computing 5(2): 133-149.

M. Egenhofer (1993a) Definitions of Line-Line Relations for Geographic Databases. IEEE Data Engineering 16(3): 40-46.

M. Egenhofer, E. Clementini, and P. di Felice (1994a) Topological Relations between Regions with Holes, International Journal of Geographical Information Systems 8(2): 129-144.

M. Egenhofer, E. Clementini, and P. di Felice (1994b) Evaluating Inconsistencies Among Multiple Representations. Sixth International Symposium on Spatial Data Handling, Edinburgh, Scotland, pp. 901-920, Taylor & Francis, London.

M. Egenhofer and R. Franzosa (1995) On the Equivalence of Topological Relations. International Journal of Geographical Information Systems 9(2): 133-152.

D. Mark and M. Egenhofer (1993) Modeling Spatial Relations Between Lines and Regions: Combining Formal Mathematical Models and Human Subjects Testing. Cartography and Geographic Information Systems 21(3): 195-212.

D. Papadias, Y. Theodoridis, T. Sellis, and M. Egenhofer (1995) Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-Trees, SIGMOD '95, San Jose, CA, M. Carey and D. Schneider (eds.), SIGMOD RECORD 24(2): 92-103.

J. Sharma (1998) Integrated Topology- and Distance Reasoning in Geographic Information Systems, ESF-NSF Young Scholars Summer Institute, Berlin, Germany, M. Craglia and H. Onsrud (eds.), Taylor & Francis, London (in press).

J. Sharma, D. Flewelling, and M. Egenhofer (1994) A Qualitative Spatio-Temporal Reasoner. Sixth International Symposium on Spatial Data Handling, Edinburgh, Scotland, Taylor & Francis, pp. 665-681.

Area Background

Geographic information systems (GIS) has become a booming technology over the last 10 years. The theoretical underpinning of GIS is the interdisciplinary field of geographic information science. Geographic information science incorporates such diverse and different perspectives as cognitive aspects of geographic space, the development of computational methods for geographic concepts, and the societal implications of the use of geographic information systems. Most relevant for IDM is the bridge between the cognitive aspects and the computational implementations. For the successful design of GISs, it is critical that any formalization and implementation captures appropriately the semantics the users employ about geospatial information. The lack of cognitively plausible and comprehensive spatial algebras has often led to ad-hoc approaches in GIS design. Spatial database systems are an important part of a GIS as the repository for geospatial data and as a means to access geospatial data. Spatial access methods have been among the most popular research topics in this area, often however disregarding particular properties of geographic data. Spatial query languages, such as extensions to SQL, have also found attention, with some of the results now being fed into SQL/Multimedia. Over the last 5-10 years, the semantics of spatial relations have found most attention in the spatial-database research community.

In the US, the academic GIS field is organized under an umbrella organization, the University Consortium for Geographic Information Science (UCGIS) with approximately 45 member institutions. UCGIS has developed a 10-point research priority list (see http://www.ucgis.org) including some topics relevant to IDM. UCGIS is also developing education priorities, ranging from K-12 education to the certification of GIS professionals. The Open GIS Consortium (OGC) attempts to establish interoperability specifications through vendor-user interactions (http://www.opengis.org). In the research area, the most prominent and visible activities have been launched by the National Center for Geographic Information and Analysis (NCGIA). Currently NCGIA is conducting an NSF-funded project to advance geographic information science (http://www.ncgia.org/varenius), which includes research-agenda setting procedures in Interoperating Geographic Information Systems, Ontology of Fields, and Discovering Geographic Knowledge in Data-Rich Environments.

The GIS field is well established and has a large number of international and national conferences, such as the Symposium on Spatial Data Handling, Autocarto, the Symposium on Large Spatial Databases, and the Conference on Spatial Information Theory. Its journals include among others the International Journal of Geographical Information Science, Geoinformatica, and Transactions in GIS.

Area References

M. Egenhofer and R. Franzosa (1991) Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems 5(2): 161-174.

 M. Egenhofer and J. Herring, Eds. (1995) Advances in Spatial Databases--4th International Symposium, SSD '95, Portland, ME. Lecture Notes in Computer Science 951. Springer-Verlag, Berlin.

A. Frank (1982) MAPQUERY--Database Query Language for Retrieval of Geometric Data and its Graphical Representation. ACM Computer Graphics 16(3): 199-207.

R. GŸting (1994) An Introduction to Spatial Database Systems. VLDB Journal 3(4): 357-399.

S. Hirtle and A. Frank, Eds. (1997) Spatial Information Theory--A Theoretical Basis for GIS, International Conference COSIT '97, Laurel Highlands, PA. Springer-Verlag, Berlin.

D. Maguire, M. Goodchild, and D. Rhind, Eds. (1991) Geographical Information Systems. Longman, London.

D. Mark and A. Frank, Eds. (1991) Cognitive and Linguistic Aspects of Geographic Space. Kluwer Academic Publishers, Dordrecht.

D. Papadias and T. Sellis (1995) A Pictorial Query-by-Example Language. Journal of Visual Languages and Computing 6(1): 53-72.

M. Worboys (1996) GIS: A Computing Perspective. Taylor & Francis, London.