Andrew Frank, who retired in September 2016 from the chair of geoinformation position at the Vienna University of Technology that he had held for a quarter century, has had anextraordinary influenc...

Surrounds is a topological relation that can exist between two regions or between collections of regions in R2. This paper provides an algebraic construction for surrounds within a partition and provides a complementary graph-theoretic approach for the detection of the surrounds conditions created by the operations within the algebra. These two approaches are contrasted to one another. Constraints are placed upon surrounds to maintain certain algebraic benefits and the consequences of their relaxations are assessed.

Naive Geography's premise "Topology matters, metric refines" calls for metric properties that provide opportunities for finergrained distinctions than the purely qualitative topological relations. This paper defines a comprehensive set of eleven metric refinements that apply to the eight coarse topological relations between two regions that the 9-intersection and the Region-Connection Calculus identify and develops the applicable value ranges for each metric refinement. It is shown that any topological relation between two regions can be derived uniquely from the conjunction of at most three such refinement specifications (i.e., pairs of metric refinements and applicable value ranges). The smallest set of refinement specifications that determine uniquely all eight relations resorts to six of the eleven metric refinements.

Forty-four relations are found between an interval and an interval with a gap ( rIIg), capturing semantics that are distinct from those of the sets of constituting intervals and at a higher semantic level than pure point-based models. The relations' conceptual neighborhood graph evolves as a refinement of the graph of Allen's thirteen binary relations between intervals, primary due to more details revealed about five of the thirteen interval relations. The compositions of rIIgwith their converse relations rIgIreveal that the interval compositions form an upper bound within which the gaps reduce the set of possible inferences, sometimes up to yielding unique inferences where interval compositions are fully undetermined.

Many real and artificial entities in geographic space, such as transportation networks and trajectories of movement, are typically modelled as lines in geographic information systems. In a similar fashion, people also perceive such objects as lines and communicate about them accordingly as evidence from research on sketching habits suggests. To facilitate new modalities like sketching that rely on the similarity between qualitative representations, oftentimes multi‐resolution models are needed to allow comparisons between sketches and database scenes through successively increasing levels of detail. Within such a setting, topology alone is sufficient only for a coarse estimate of the spatial similarity between two scenes, whereas metric refinements may help extract finer details about the relative positioning and geometry between the objects. The nine‐intersection is a topological model that distinguishes 33 relations between two lines based on the content invariant (empty–non‐empty intersections) among boundaries, interiors, and exteriors of the lines. This paper extends the nine‐intersection model by capturing metric details for line–line relations through splitting ratios and closeness measures. Splitting ratios, which apply to the nine‐intersection's non‐empty values, are normalized values of lengths and areas of intersections. Closeness measures, which apply to the nine‐intersection's empty values, are normalized distances between disjoint object parts. Both groups of measures are integrated into compact representations of topological relations, thereby addressing topological and metric properties of arbitrarily complex line–line relations.

Semantic similarity plays an important role in geographic information systems as it supports the identification of objects that are conceptually close, but not identical. Similarity assessments are particularly important for retrieval of geospatial data in such settings as digital libraries, heterogeneous databases, and the World Wide Web. Although some computational models for semantic similarity assessment exist, these models are typically limited by their inability to handle such important cognitive properties of similarity judgements as their inherent asymmetry and their dependence on context. This paper defines the Matching-Distance Similarity Measure (MDSM) for determining semantic similarity among spatial entity classes, taking into account the distinguishing features of these classes (parts, functions, and attributes) and their semantic interrelations (is–a and part–whole relations). A matching process is combined with a semantic-distance calculation to obtain asymmetric values of similarity that depend on the degree of generalization of entity classes. MDSM's matching process is also driven by contextual considerations, where the context determines the relative importance of distinguishing features. Based on a human-subject experiment, MDSM results correlate well with people's judgements of similarity. When contextual information is used for determining the importance of distinguishing features, this correlation increases; however, the major component of the correlation between MDSM results and people's judgements is due to a detailed definition of entity classes.

Semantic similarity measures play an important role in information retrieval and information integration. Traditional approaches to modeling semantic similarity compute the semantic distance between definitions within a single ontology. This single ontology is either a domain-independent ontology or the result of the integration of existing ontologies. We present an approach to computing semantic similarity that relaxes the requirement of a single ontology and accounts for differences in the levels of explicitness and formalization of the different ontology specifications. A similarity function determines similar entity classes by using a matching process over synonym sets, semantic neighborhoods, and distinguishing features that are classified into parts, functions, and attributes. Experimental results with different ontologies indicate that the model gives good results when ontologies have complete and detailed representations of entity classes. While the combination of word matching and semantic neighborhood matching is adequate for detecting equivalent entity classes, feature matching allows us to discriminate among similar, but not necessarily equivalent entity classes.

To support users in querying geographic databases we have developed a system that lets people sketch what they are looking for. It closes the gap between user and information system, because the translation of a user's question into a processable query statement is delegated to the information system so that a user can focus on the actual query rather than spending time with its formulation. This system paper highlights a set of interaction methods and sketch interpretation algorithms that are necessary for pen-based querying of geographic information systems. They are part of a comprehensive prototype implementation of Spatial-Query-by-Sketch, which provides feature-based and relation-based spatial similarity retrieval.

As efforts grow to develop spatio-temporal database systems and temporal geographical information systems that are capable of conveying how geographical phenomena change, it is important to distinguish the elements that are fundamental to scenarios of change. This paper presents a model based on the explicit description of change with respect to states of existence and non-existence for identifiable objects. Such changes are of concern when, for instance, modelling and reasoning about nations that are subsumed through conflict only to return once more at a later time, or about water bodies that fluctuate due to seasonal or climatic change. The basis for tracing these changes is the concept of object identity. Identity, distinct from an object's properties, values, or structure, is that unique characteristic that distinguishes one object from another. Based on a small set of primitives relating to the identity states of objects, we model the semantics associated with change and through a systematic derivation, a complete set of identity-based change operations evolves from the primitives. These operations are basic to the types of change commonly experienced by geographical phenomena and modelled by researchers studying spatio-temporal change. This approach highlights the minimum elements necessary for reasoning about change, namely, object identity, an ordering of identity states, and co-occurrence of identity states.

Over the past ten years, a subfield of GIScience has been recognized that addresses the linkage between human thought regarding geographical space, and the mechanisms for implementing these concepts in computational models. This research area has developed an identity through a series of successful international conferences and the establishment of a journal. It has also been complemented through community activities such as international standardization efforts and GIS interoperability. Historically, much of the advancement in computational methods has occurred at or close to the implementation level, as exemplified by attention to the development of spatial access methods. Significant progress has been made at the levels of spatial data models and spatial query languages, although we note the lack of a comprehensive theoretical framework comparable to the relational data model in database management systems. The difficult problems that need future research efforts are at the highly abstract level of capturing semantics of geographical information. A cognitive motivation is most promising as it shapes the focus on the users' needs and points of view, rather than on efficiency as in the case of a bottom-up system design. We also identify the need for new research in fields, models of qualitative spatial information, temporal aspects, knowledge discovery, and the integration of GIS with database management systems.

This paper introduces a special issue of the journal on the subject of Project Varenius, a three-year effort funded by the US National Science Foundation to advance geographical information science. Geographical information is first defined as an abstraction of primitive tuples linking geographical locations to general descriptors. Geographical concepts originate in the human mind, and are instantiated in geographical information. Geographical information technologies apply digital methods to geographical information. Finally, geographical information science is defined as the set of basic research issues arising from these technologies. Three motivations are presented for research in this area: scientific, technological, and societal. Within the project, geographical information science is structured by a three-part framework that includes cognitive, computational, and societal issues. The paper ends with an introduction to these three parts, which define the infrastructure of the project and are discussed at length by the subsequent three papers.

Spatial relations often are desired answers that a geographic information system (GIS) should generate in response to a user's query. Current GIS's provide only rudimentary support for processing and interpreting natural-language-like spatial relations, because their models and representations are primarily quantitative, while natural-language spatial relations are usually dominated by qualitative properties. Studies of the use of spatial relations in natural language showed that topology accounts for a significant portion of the geometric properties. This article develops a formal model that captures metric details for the description of natural-language spatial relations. The metric details are expressed as refinements of the categories identified by the 9-intersection, a model for topological spatial relations, and provide a more precise measure than does topology alone as to whether a geometric configuration matches with a spatial term or not. Similarly, these measures help in identifying the spatial term that describes a particular configuration. Two groups of metric details are derived: splitting ratios as the normalized values of lengths and areas of intersections; and closeness measures as the normalized distances between disjoint object parts. The resulting model of topological and metric properties was calibrated for 64 spatial terms in English, providing values for the best fit as well as value ranges for the significant parameters of each term. Three examples demonstrate how the framework and its calibrated values are used to determine the best spatial term for a relationship between two geometric objects.

No abstract available.

Recent developments in spatial relations have led to their use in numerous applications involving spatial databases. This paper is concerned with the retrieval of topological relations in Minimum Bounding Rectangle-based data structures. We study the topological information that Minimum Bounding Rectangles convey about the actual objects they enclose, using the concept of projections. Then we apply the results to R-trees and their variations, R+-trees and R*-trees in order to minimise disk accesses for queries involving topological relations. We also investigate queries that involve complex spatial conditions in the form of disjunctions and conjunctions and we discuss possible extensions.

The 4-intersection, a model for binary topological relations, is based on the intersections of the boundaries and interiors of two point sets in a topological space, considering the content invariant (i.e., emptiness/non-emptiness) of the intersections. If the 4-intersections of two pairs of point sets have different contents, then their topological relations are different as well; however, the reverse cannot be stated as there may be different topological relations that map onto a 4-intersection with the same content. This paper refines the model of empty/non-empty 4-intersections with further topological invariants to account for more details about topological relations. The invariants used are the dimension of the components, their types (touching, crossing, and different refinements of crossings), their relationships with respect to the exterior neighbourhoods, and the sequence of the components. These invariants, applied to non-empty boundary-boundary intersections, comprise a classification invariant for binary topological relations between homogeneously 2-dimensional, connected point sets (disks) in the plane such that if two different 4-intersections with the necessary invariants are equal, then their topological relations are identical. The model presented applies to processing G1S queries about whether or not two pairs of spatial objects have the same topological relation and gives rise to the formal definition of topological similarity.

Based on the 9-intersection for binary topological relations, two models of conceptual neighbourhoods among topological relations between a line and a region are developed. The snapshot model derives the neighbourhoods by comparing pairs of topological relations and selects neighbours based on least noticeable differences, whereas the smooth-transition model develops neighbourhoods based on the knowledge of the deformations that may change a topological relation. The resulting similarity diagrams show some differences, which were compared with the results from tests in which human subjects were asked to organized line-region relations into groups of similar relations. The groupings the subjects made indicate that the smooth-transition model captures more important aspects of the similarity of topological line-region relations than the snapshot model.

The 4-intersection, a model for the representation of topological relations between two-dimensional objects with connected boundaries and connected interiors, is extended to cover topological relations between two-dimensional objects with arbitrary holes, called regions with holes. Each region with holes is represented by its generalized region—the union of the object and its holes—and the closure of each hole. The topological relation between two regions with holes, A and B, is described by the set of all individual topological relations between (1) A's generalized region and B's generalized region, (2) A's generalized region and each of B's holes, (3) B's generalized region with each of A's holes, and (4) each of A's holes with each of B's holes. As a side product, the same formalism applies to the description of topological relations between 1-spheres. An algorithm is developed that minimizes the number of individual topological relations necessary to describe a configuration completely. This model of representing complex topological relations is suitable for a multi-level treatment of topological relations, at the least detailed level of which the relation between the generalized regions prevails. It is shown how this model applies to the assessment of consistency in multiple representations when, at a coarser level of less detail, regions are generalized by dropping holes.

Recently, attention has been focused on spatial databases, which combine conventional and spatially related data, such as geographic information systems, CAD/CAM, or VLSI. A language has been developed to query such spatial databases. It recognizes the significantly different requirements of spatial data handling and overcomes the inherent problems of the application of conventional database query languages. The spatial query language has been designed as a minimal extension to the interrogative part of SQL and distinguishes from previously designed SQL extensions by: the preservation of SQL concepts; the high-level treatment of spatial objects; and the incorporation of spatial operations and relationships. It consists of two components, a query language to describe what information to retrieve and a presentation language to specify how to display query results. Users can ask standard SQL queries to retrieve nonspatial data based on nonspatial constraints, use Spatial SQL commands to inquire about situations involving spatial data, and give instructions in the Graphical Presentation Language, GPL to manipulate or examine the graphical presentation.>

Geographic databases are becoming a popular subject for research projects. It is acknowledged that database requirements for such applications as Geographic Information Systems (GISs), computer cartography, remote-sensing image databases, and emergency routing/dispatching are distinct from those for traditional database applications; however, the specific database needs due to the properties of geographic data are frequently overlooked. Here, we describe a specific problem domain, a vehicle navigation system, and analyze the properties of data to be modeled appropriately and managed efficiently by database management systems. Vehicle navigation systems need continuous, fast access to very large databases. Through the combination of real-time access and geographic data, we identify particularly challenging database requirements of this application with respect to data models, query languages, and query processing.

Formal methods for the description of spatial relations can be based on mathematical theories of order. Subdivisions of land are represented as partially ordered sets (posets), a model that is general enough to answer spatial queries about inclusion and containment of spatial areas. After a brief introduction to the basic concepts of posets and lattices, their applications to modelling spatial relations and operations for spatial regions in terms of containment and overlay are presented. An interpretation is given for new geographical elements that are created by the completion from a poset to a lattice. It is shown that a novel approach to characterize certain topological relations based on a lattice of a simplicial complex is a model for spatial regions that combines both topological and order relations and allows spatial queries to be answered in a unified way.

The application of traditional database query languages, primarily the Structured Query Language SQL, for geographical information systems (GIS) and other non–standard database applications has been tried unsuccessfully; therefore, several extensions to the relational database query language SQL have been proposed to serve as a spatial query language. It is argued that the SQL framework is inappropriate for an interactive query language for a GIS and an extended SQL is at best a short term solution. Any spatial SQL dialect has a number of serious deficiencies, particularly the patches to incorporate the necessary spatial concepts into SQL.

Practical needs in geographic information systems (GIS) have led to the investigation of formal and sound methods of describing spatial relations. After an introduction to the basic ideas and notions of topology, a novel theory of topological spatial relations between sets is developed in which the relations are defined in terms of the intersections of the boundaries and interiors of two sets. By considering empty and non-empty as the values of the intersections, a total of sixteen topological spatial relations is described, each of which can be realized in R 2. This set is reduced to nine relations if the sets are restricted to spatial regions, a fairly broad class of subsets of a connected topological space with an application to GIS. It is shown that these relations correspond to some of the standard set theoretical and topological spatial relations between sets such as equality, disjointness and containment in the interior.