Modelling topological spatial relations: Strategies for query processing

doi:10.1016/0097-8493(94)90007-8

Computers & Graphics

Volume 18, Issue 6, November–December 1994, Pages 815-822

https://doi.org/10.1016/0097-8493(94)90007-8 Get rights and content

Abstract

This paper investigates the processing of spatial queries with topological constraints, for which current database solutions are inappropriate. Topological relations, such as disjoint, meet, overlap, inside, and contains, have been well defined by the 9-intersection, a comprehensive model for binary topological relations. We focus on two types of queries: (1) “Which objects have a stated topological relation with a given spatial object?” and (2) “What is the topological relation between two given spatial objects?” Such queries are processed at two levels of detail. First, Minimum Bounding Rectangles are used as an approximation of the objects' geometry and as a means of identifying candidates that might satisfy the query. Next, the nine intersections that determine the topological relations between candidate pairs are calculated. We present algorithms for minimizing these computations. Considerable performance can be gained by exploiting the semantics of spatial relations. We also compare the approach for a naive cost model, which assumes that all relations have the same frequency of occurrence, with a refined cost model, which considers the probability of occurrence of the topological relations. The strategies presented here have three key benefits: (1) they are based on a well-defined formalism; (2) they are customizable; and (3) they can take into account important statistical information about the data.

References (24)

C. Freksa
Temporal reasoning based on semi-intervals
Artificial Intelligence
(1992)
O. Günther et al.
Research issues in spatial databases
SIGMOD Record
(1990)
M.J. Egenhofer
Reasoning about binary topological relations
D.S. Batory et al.
Implementation concepts for an extensible data model and language
ACM Transactions on Database Systems
(1988)
M.J. Egenhofer et al.
Point-set topological spatial relations
Int. J. Geo. Info. Sys.
(1991)
M.J. Egenhofer et al.
Categorizing Binary Topological Relationships Between Regions, Lines, and Points in Geographic Databases
J.R. Herring et al.
Extensions to the SQL language to support spatial analysis in a topological data base
D. Mark et al.
An evaluation of the 9-intersection for region-line relations
M.J. Egenhofer et al.
Reasoning about gradual changes of topological relationships
M.J. Egenhofer et al.
A topological data model for spatial databases

J. Herring

The mathematical modeling of spatial and non-spatial information in geographic information systems

M.J. Egenhofer

Why not SQL!

Int. J. Geo. Info. Sys.

(1992)

Cited by (206)

Three-dimensional Geospatial Interlinking with JedAI-spatial
2024, Journal of Web Semantics
Geospatial data constitutes a considerable part of Semantic Web data, but so far, its sources are inadequately interlinked in the Linked Open Data cloud. Geospatial Interlinking aims to cover this gap by associating geometries with topological relations like those of the Dimensionally Extended 9-Intersection Model. Due to its quadratic time complexity, various algorithms aim to carry out Geospatial Interlinking efficiently. We present JedAI-spatial, a novel, open-source system that organizes these algorithms according to three dimensions: (i) Space Tiling, which determines the approach that reduces the search space, (ii) Budget-awareness, which distinguishes interlinking algorithms into batch and progressive ones, and (iii) Execution mode, which discerns between serial algorithms, running on a single CPU-core, and parallel ones, running on top of Apache Spark. We analytically describe JedAI-spatial’s architecture and capabilities and perform thorough experiments to provide interesting insights about the relative performance of its algorithms.
Detecting changes in spatial characteristics of Colorado human-caused wildfires using APRIORI-based frequent itemset mining
2023, Computers, Environment and Urban Systems
The phenomenon of human-caused wildfire presents significant dilemmas for states like Colorado, given a growing population and large portions of forested mountain ecoregions. This study seeks to understand the changes in characteristics of Western Colorado human-caused wildfire (HCF) occurrences from 1992 to 2015 while considering their locations and spatial context. Fires are grouped into three seven-year study periods, 1992–1999, 2000–2007, and 2008–2015. First, we constructed an extensive spatial database documenting the spatial characteristics of these fires. The spatial characteristics represent the spatial relationships and interactivity of fire occurrence locations with various environmental and anthropogenic entities. Second, an unsupervised data mining approach (APRIORI-based itemset mining) is used to extract the most frequent characteristics of the fire occurrences during these periods. Finally, we present a comprehensive visual graph-based evaluation approach to evaluate the mined results effectively. Our findings indicate explicit and fresh insights into changes in human-caused wildfire characteristics for the study area. The method presented and enhanced here is proven robust and very effective at extracting an extensive and comprehensive set of characteristics of HCFs. The operative spatial predication schemas and the result evaluation approach based on visual analytics are this study's successful and novel aspects.
Navigating planar topologies in near-optimal space and time
2023, Computational Geometry: Theory and Applications
We show that any embedding of a planar graph can be encoded succinctly while efficiently answering a number of topological queries near-optimally. More precisely, we build on a succinct representation that encodes an embedding of m edges within 4m bits, which is close to the information-theoretic lower bound of about 3.58m. With $4 m + o (m)$ bits of space, we show how to answer a number of topological queries relating nodes, edges, and faces, most of them in any time in $ω (1)$ . Indeed, $3.58 m + o (m)$ bits suffice if the graph has no self-loops and no nodes of degree one. Further, we show that with $O (m)$ bits of space we can solve all those operations in $O (1)$ time.
Accessing interactively the spatio-temporal data-model of an archaeological site through its 3D virtual reconstruction
2022, Digital Applications in Archaeology and Cultural Heritage
Citation Excerpt :
Topological operators have already been studied in archaeology (Belussi and Migliorini, 2017). The topological model named “Dimensionally Extended Nine-Intersection Model” (DE-9IM) is defined as a 3x3 matrix which determines the spatial relations between two 2D geometries (Clementini et al., 1994). This matrix can be extended to 3D as a more complex 5x5 matrix or 25-intersection model (Zhou and Guan, 2019).
Information and communication technologies are increasingly used in all archaeological processes. However, archaeologists sometimes consider them as intrusive, too far from the traditional work methodology and even a hindrance. In this article we propose a framework to allow natural and therefore intuitive access to the archaeological record. The information retrieval process is carried out through a three-dimensional virtual reconstruction of the archaeological site. In this system, navigation and interaction with the three-dimensional elements of the environment triggers database queries. To achieve such functionality, a client-server architecture is designed in which the server maintains a spatio-temporal database with heterogeneous information, including the 3D models of the finds. To do this, a virtual replica of the site is created considering spatial restrictions and topological relationships among the finds.
Geoscience-aware deep learning: A new paradigm for remote sensing
2022, Science of Remote Sensing
Information extraction is a key activity for remote sensing images. A common distinction exists between knowledge-driven and data-driven methods. Knowledge-driven methods have advanced reasoning ability and interpretability, but have difficulty in handling complicated tasks since prior knowledge is usually limited when facing the highly complex spatial patterns and geoscience phenomena found in reality. Data-driven models, especially those emerging in machine learning (ML) and deep learning (DL), have achieved substantial progress in geoscience and remote sensing applications. Although DL models have powerful feature learning and representation capabilities, traditional DL has inherent problems including working as a black box and generally requiring a large number of labeled training data. The focus of this paper is on methods that integrate domain knowledge, such as geoscience knowledge and geoscience features (GK/GFs), into the design of DL models. The paper introduces the new paradigm of geoscience-aware deep learning (GADL), in which GK/GFs and DL models are combined deeply to extract information from remote sensing data. It first provides a comprehensive summary of GK/GFs used in GADL, which forms the basis for subsequent integration of GK/GFs with DL models. This is followed by a taxonomy of approaches for integrating GK/GFs with DL models. Several approaches are detailed using illustrative examples. Challenges and research prospects in GADL are then discussed. Developing more novel and advanced methods in GADL is expected to become the prevailing trend in advancing remotely sensed information extraction in the future.
Spatial concept learning and inference on geospatial polygon data
2022, Knowledge-Based Systems
Geospatial knowledge has always been an essential driver for many societal aspects. This concerns in particular urban planning and urban growth management. To gain insights from geospatial data and guide decisions usually authoritative and open data sources are used, combined with user or citizen sensing data. However, we see a great potential for improving geospatial analytics by combining geospatial data with the rich terminological knowledge, e.g., provided by the Linked Open Data Cloud. Having semantically explicit, integrated geospatial and terminological knowledge, expressed by means of established vocabularies and ontologies, cross-domain spatial analytics can be performed. One analytics technique working on terminological knowledge is inductive concept learning, an approach that learns classifiers expressed as logical concept descriptions. In this paper, we extend inductive concept learning to infer and make use of the spatial context of entities in spatio-terminological data. We propose a formalism for extracting and making spatial relations explicit such that they can be exploited to learn spatial concept descriptions, enabling ‘spatially aware’ concept learning. We further provide an implementation of this formalism and demonstrate its capabilities in different evaluation scenarios.

View all citing articles on Scopus

^†: This work was performed while on a leave of absence from Università di L'Aquila, Dipartimento di Ingegneria Elettrica, 67040 Poggio di Roio, L'Aquila, Italy. Eliseo Clementini is partially supported by the Italian National Council of Research (CNR) under Grant No. 92.01574.PF69.

^§: Max Egenhofer's work is partially supported by NSF Grant No. IRI-9309230, a grant from Intergraph Corporation, a University of Maine Summer Faculty Research Grant, and the NCGIA through NSF Grant No. SBR-8810917.

View full text

Modelling and visualization of spatial data in GISModelling topological spatial relations: Strategies for query processing

Abstract

Artificial Intelligence

Research issues in spatial databases

SIGMOD Record

Reasoning about binary topological relations

Implementation concepts for an extensible data model and language

ACM Transactions on Database Systems

Point-set topological spatial relations

Int. J. Geo. Info. Sys.

Categorizing Binary Topological Relationships Between Regions, Lines, and Points in Geographic Databases

Extensions to the SQL language to support spatial analysis in a topological data base

An evaluation of the 9-intersection for region-line relations

Reasoning about gradual changes of topological relationships

A topological data model for spatial databases

The mathematical modeling of spatial and non-spatial information in geographic information systems

Why not SQL!

Int. J. Geo. Info. Sys.

Modelling and visualization of spatial data in GIS
Modelling topological spatial relations: Strategies for query processing