Topological data analysis (TDA) is an emerging field of research, which considers the application of topology to data analysis. Recently, these methods have been successfully applied to research problems in the field of geographical information science (GIS) and there is much potential for future applications. In this article, we provide an introduction to the fundamentals of TDA for GIS researchers and practitioners and highlight specific benefits that TDA methods provide relative to some conventional methods. We focus on the method of persistent homology, which is the most commonly used TDA method. We describe how persistent homology can be applied to data types commonly encountered in the GIScience domain, namely sets of points, networks and sequences of images. We also describe the application of persistent homology to two specific GIS problems, which are the point pattern analysis of UK city pubs and the analysis of UK rainfall radar imagery. In each case we stress the specific benefits of TDA methods that include, for example, generating an output signature in a form that can be subject to subsequent analyses; identification of void regions in point patterns; and providing a relatively simple method to track objects in spatio-temporal images.

Natural language location descriptions frequently describe object locations relative to other objects (the house near the river). Geospatial prepositions (e.g.near) are a key element of these descriptions, and the distances associated with proximity, adjacency and topological prepositions are thought to depend on the context of a specific scene. When referring to the context, we include consideration of properties of the relatum such as its feature type, size and associated image schema. In this paper, we extract spatial descriptions from the Google search engine for nine prepositions across three locations, compare their acceptance thresholds (the distances at which different prepositions are acceptable), and study variations in different contexts using cumulative graphs and scatter plots. Our results show that adjacency prepositions next to and adjacent to are used for a large range of distances, in contrast to beside; and that topological prepositions in, at and on can all be used to indicate proximity as well as containment and collocation. We also found that reference object image schema influences the selection of geospatial prepositions such as near and in.

A considerable proportion of records that describe biological specimens (flora, soil, invertebrates), and especially those that were collected decades ago, are not attached to corresponding geographical coordinates, but rather have their location described only through textual descriptions (e.g. North Canterbury, Selwyn River near bridge on Springston-Leeston Rd). Without geographical coordinates, millions of records stored in museum collections around the world cannot be mapped. We present a method for predicting the distance and direction associated with human language location descriptions which focuses on the interpretation of geospatial prepositions and the way in which they modify the location represented by an associated reference place name (e.g. near the Manawatu River). We study eight distance-oriented prepositions and eight direction-oriented prepositions and use machine learning regression to predict distance or direction, relative to the reference place name, from a collection of training data. The results show that, compared with a simple baseline, our model improved distance predictions by up to 60% and direction predictions by up to 31%.

Natural language descriptions of geographical locations are used frequently in daily life and there is a motivation to create systems that generate such descriptions automatically, for purposes such as documentation of where events have taken place, where a person is located, where photos were taken and where plants and animals are located. Typically location descriptions combine references to named geographical features with vague spatial relational terms, such as near, north of and at that relate locations to the features. Here we describe a system for generating location descriptions, that combines spatial templates, that model the applicability of different spatial relations relative to a reference location, with toponyms in the vicinity of the described location that are selected according to aspects of salience. The toponyms are retrieved from a gazetteer service based on OpenStreetMap for which we create a hierarchical feature classification scheme to facilitate selection of toponyms according to distinctiveness of their feature types and other aspects of salience. The advantages of the approach are demonstrated in a user study, relative to an existing state of the art system and to other baseline approaches that include manually created captions and the automated methods of two widely used photo captioning systems.

References to geographic locations are common in text data sources including social media and web pages. They take different forms from simple place names to relative expressions that describe location through a spatial relationship to a reference object (e.g. the house beside the Waikato River). Often complex, multi-word phrases are employed (e.g. the road and railway cross at right angles; the road in line with the canal) where spatial relationships are communicated with various parts of speech including prepositions, verbs, adverbs and adjectives. We address the problem of automatically detecting relative geospatial location descriptions, which we define as those that include spatial relation terms referencing geographic objects, and distinguishing them from non-geographical descriptions of location (e.g. the book on the table). We experiment with several methods for automated classification of text expressions, using features for machine learning that include bag of words that detect distinctive words, word embeddings that encode meanings of words and manually identified language patterns that characterise geospatial expressions. Using three data sets created for this study, we find that ensemble and meta-classifier approaches, that variously combine predictions from several other classifiers with data features, provide the best F-measure of 0.90 for detecting geospatial expressions.

There is increasing interest in detecting the presence of geospatial locative expressions that include spatial relation terms such as near or within . Being able to do so provides a foundation for interpreting relative descriptions of location and for building corpora that facilitate the development of methods for spatial relation extraction and interpretation. Here we evaluate the use of a spatial role labelling procedure to distinguish geospatial uses of prepositions from other spatial and non-spatial uses and experiment with the use of additional machine learning features to improve the quality of detection of geospatial prepositions. An annotated corpus of nearly 2000 instances of preposition usage was created for training and testing the classifiers.

In many instances of the object tracking problem the topological properties of objects can change over time. Such changes include the splitting of an object into multiple objects or merging of multiple objects into a single object. We propose a novel tracking model which is robust to such changes. This model is formulated terms of homology theory whereby 0-dimensional homology classes, which correspond to path-connected components, are tracked. A generalisation of this model for tracking spatially close objects lying in an ambient metric space is also proposed. This generalisation is particularly suitable for tracking spatial-temporal phenomena such as weather phenomena. The utility of the proposed model is demonstrated with respect to tracking rain clouds in radar imagery.

The photo-sharing website Flickr has become a valuable informal information source in disciplines such as geography and ecology. Some ecologists, for instance, have been manually analysing Flickr to obtain information that is more up-to-date than what is found in traditional sources. While several previous works have shown the potential of Flickr tags for characterizing places, it remains unclear to what extent such tags can be used to derive scientifically useful information for ecologists in an automated way. To obtain a clearer picture about the kinds of environmental features that can be modelled using Flickr tags, we consider the problem of predicting scenicness, species distribution, land cover, and several climate related features. Our focus is on comparing the predictive power of Flickr tags with that of structured data from more traditional sources. We find that, broadly speaking, Flickr tags perform comparably to the considered structured data sources, being sometimes better and sometimes worse. Most importantly, we find that combining Flickr tags with structured data sources consistently, and sometimes substantially, improves the results. This suggests that Flickr indeed provides information that is complementary to traditional sources.

We propose a method for modeling the topology of swarm behavior in a manner which facilitates the application of machine learning techniques such as clustering. This is achieved by modeling the persistence of topological features, such as connected components and holes, of the swarm with respect to time using zig-zag persistent homology. The output of this model is subsequently transformed into a representation known as a persistence landscape. This representation forms a vector space and therefore facilitates the application of machine learning techniques. The proposed model is validated using a real data set corresponding to a swarm of 300 fish. We demonstrate that it may be used to perform clustering of swarm behavior with respect to topological features.

Gazetteers play an essential role in GIS in translating between place name and coordinate-based descriptions of location. The proliferation of location-aware social media applications has led to new sources of gazetteer data, many of which are crowd-sourced. They complement the conventional authoritative resources that are typically linked to published map products. We illustrate the variation in performance of several, mostly social media based, gazetteer resources for a reverse-geocoding photo captioning task and demonstrate the advantage of a meta-gazetteer service that integrates multiple individual gazetteer resources and employs several toponym ranking methods.

Social media sources such as Flickr and Twitter continuously generate large amounts of textual information (tags on Flickr and short messages on Twitter). This textual information is increasingly linked to geographical coordinates, which makes it possible to learn how people refer to places by identifying correlations between the occurrence of terms and the locations of the corresponding social media objects. Recent work has focused on how this potentially rich source of geographic information can be used to estimate geographic coordinates for previously unseen Flickr photos or Twitter messages. In this article, we extend this work by analysing to what extent probabilistic language models trained on Flickr and Twitter can be used to assign coordinates to Wikipedia articles. Our results show that exploiting these language models substantially outperforms both (i) classical gazetteer-based methods (in particular, using Yahoo! Placemaker and Geonames) and (ii) language modelling approaches trained on Wikipedia alone. This supports the hypothesis that social media are important sources of geographic information, which are valuable beyond the scope of individual applications.

The current web is rich in geographically referenced data. Mining, retrieving and sharing these data raises the need for rich geographical place name resources that record spatial and thematic elements of geographical places. Here, possible services offered at a place and human activities that can be practised there are considered useful concepts to discover and encode in place name resources. Recognising this dimension of place description can enhance information retrieval tasks by extending the range of possible queries and search criteria that relate to different place instances. This work proposes an automatic approach for the identification and extraction of service and activity-related concepts from multiple resources of textual descriptions of geographical place types. Frequent affordance patterns are identified and then applied to a corpus of resources to extract service and activity types associated with specific geographical place types. The evaluation experiments undertaken demonstrate the potential value of the approach.

Many aspects of spatial language concerned with relationships between spatial entities are essentially vague. Current GIS technology provides very little support for dealing with this vagueness, partially because there is a lack of quantitative data and models for vague spatial relations. This paper presents an experiment that looks at quantifying spatial prepositions. In the context of image captions, the cardinal directions are analysed in an existing set of image captions, with respect to the spatial distribution of the locations of the target object (figure) and the reference object (ground). Future work will focus on using these results to improve current GIS solutions in a wide variety of scenarios.

The World Wide Web has become the world's largest networked information resource, but references to geographical locations remain unstructured and typically implicit in nature. This lack of explicit spatial knowledge within the Web makes it difficult to service user needs for location-specific information. At present, spatial knowledge is hidden in many small information fragments such as addresses on Web pages, annotated photos with GPS co-ordinates, geographic mapping applications, and geotags in user-generated content. Several emerging formats that primarily or secondarily include location metadata, like GeoRSS, KML, and microformats, aim to improve this state of affairs. However, the question remains how to extract, index, mine, find, view, mashup, and exploit Web content using its location semantics. This work-shop brings together researchers from academia and industry labs to discuss and present the latest results and trends in all facets of the relationships between location concepts and Web information.

Geographical information is recorded in a wide variety of media and document types. There are innumerable paper‐based books, reports, images and maps, and there are computer databases and digital m...

Place names are often used to describe and to enquire about geographical information. It is common for users to employ vernacular names that have vague spatial extent and which do not correspond to the official and administrative place name terminology recorded within typical gazetteers. There is a need therefore to enrich gazetteers with knowledge of such vague places and hence improve the quality of place name‐based information retrieval. Here we describe a method for modelling vague places using knowledge harvested from Web pages. It is found that vague place names are frequently accompanied in text by the names of more precise co‐located places that lie within the extent of the target vague place. Density surface modelling of the frequency of co‐occurrence of such names provides an effective method of representing the inherent uncertainty of the extent of the vague place while also enabling approximate crisp boundaries to be derived from contours if required. The method is evaluated using both precise and vague places. The use of the resulting approximate boundaries is demonstrated using an experimental geographical search engine.

Much of the information stored on the web contains geographical context, but current search engines treat such context in the same way as all other content. In this paper we describe the design, implementation and evaluation of a spatially aware search engine which is capable of handling queries in the form of the triplet of ⟨theme⟩⟨spatial relationship⟩⟨location⟩. The process of identifying geographic references in documents and assigning appropriate footprints to documents, to be stored together with document terms in an appropriate indexing structure allowing real‐time search, is described. Methods allowing users to query and explore results which have been relevance‐ranked in terms of both thematic and spatial relevance have been implanted and a usability study indicates that users are happy with the range of spatial relationships available and intuitively understand how to use such a search engine. Normalised precision for 38 queries, containing four types of spatial relationships, is significantly higher (p<0.001) for searches exploiting spatial information than pure text search.

Geographic information represents our understanding of the association of phenomena with their location on and near the Earth's surface. When presented in map form, an essential aspect of that info...

This paper explores the use of the stochastic optimization technique of simulated annealing for map generalization. An algorithm is presented that performs operations of displacement, size exaggeration, deletion and size reduction of multiple map objects in order to resolve graphic conflict resulting from map scale reduction. It adopts a trial position approach in which each of n discrete polygonal objects is assigned k candidate trial positions that represent the original, displaced, size exaggerated, deleted and size reduced states of the object. This gives rise to a possible kn distinct map configurations; the expectation is that some of these configurations will contain reduced levels of graphic conflict. Finding the configuration with least conflict by means of an exhaustive search is, however, not practical for realistic values of n and k. We show that evaluation of a subset of the configurations, using simulated annealing, can result in effective resolution of graphic conflict.

No abstract available.

A method is presented for generalising cartographic lines using an approach based on determination of their structure. Constrained Delaunay triangulation is used to construct a skeleton of the space surrounding the lines and hence represent line features in terms of skeleton branches. Several statistical measures are used to characterise the triangulation branches. The measures enable selective generalisation of different types of line feature, leading to the possibility of user-specification of the style of generalisation. In our implementation of the approach, the triangulation is updated dynamically to allow both sides of multiple lines to be processed, while guaranteeing topological consistency between the resulting generalised lines.

Gazeteers and geographical thesauri can be regarded as parsimonious spatial models that associate geographical location with place names and encode some semantic relations between the names. They are of particular value in processing information retrieval requests in which the user employs place names to specify geographical context. Typically the geometric locational data in a gazetteer are confined to a simple footprint in the form of a centroid or a minimum bounding rectangle, both of which can be used to link to a map but are of limited value in determining spatial relationships. Here we describe a Voronoi diagram method for generating approximate regional extents from sets of centroids that are respectively inside and external to a region. The resulting approximations provide measures of areal extent and can be used to assist in answering geographical queries by evaluating spatial relationships such as distance, direction and common boundary length. Preliminary experimental evaluations of the method have been performed in the context of a semantic modelling system that combines the centroid data with hierarchical and adjacency relations between the associated place names.

The proximity relations inherent in triangulations of geometric data can be exploited in the implementation of nearest-neighbour search procedures. This is relevant to applications such as terrain analysis, cartography and robotics, in which triangulations may be used to model the spatial data. Here we describe neighbourhood search procedures within constrained Delaunay triangulations of the vertices of linear objects, for the queries of nearest object to an object and the nearest object to an arbitrary point. The procedures search locally from object edges, or from a query point, to build triangulated regions that extend from the source edge or point by a distance at least equal to that to its nearest neighbouring feature. Several geographical datasets have been used to evaluate the procedures experimentally. Average numbers of edge–edge distance calculations to find the nearest line feature edge disjoint to another line feature edge ranged between 15 and 39 for the different datasets examined, while the average numbers of point–edge distance calculations to determine the nearest edge to an arbitrary point ranged between 7 and 35.

This paper focuses on the consistency issues related to integrating multiple sets of spatial data in spatial information systems such as Geographic Information Systems (GISs). Data sets to be integrated are assumed to hold information about the same geographic features which can be drawn from different sources at different times, which may vary in reliability and accuracy, and which may vary in the scale of presentation resulting in possible multiple spatial representations for these features. A systematic approach is proposed which relies first on breaking down the consistency issue by identifying a range of consistency classes which can be checked in isolation. These classes are a representative set of properties and relationships which can completely identify the geographic objects in the data sets. Different levels of consistency are then proposed, namely, total, partial and conditional, which can be checked for every consistency class. This provides the flexibility for two data sets to be integrated without necessarily being totally consistent in every aspect. The second step of the proposed approach is to explicitly represent the different classes and levels of consistency in the system. As an example, a simple structure which stores adjacency relationships is given which can be used for the explicit representation of topological consistency. The paper also proposes that the set of consistent knowledge in the data sets (which is mostly qualitative) be explicitly represented in the database and that uncertainty or ambiguity inherent in the knowledge be represented as well.

Growth in the available quantities of digital geographical data has led to major problems in maintaining and integrating data from multiple sources, required by users at differing levels of generalization. Existing GIS and associated database management systems provide few facilities specifically intended for handling spatial data at multiple scales and require time consuming manual intervention to control update and retain consistency between representations. In this paper the GEODYSSEY conceptual design for a multi-scale, multiple representation spatial database is presented and the results of experimental implementation of several aspects of the design are described. Object-oriented, deductive and procedural programming techniques have been applied in several contexts: automated update software, using probabilistic reasoning; deductive query processing using explicit stored semantic and spatial relations combined with geometric data; multiresolution spatial data access methods combining poini, line, area and surface geometry; and triangulation-based generalization software that detects and resolves topological inconsistency.

The triangulated irregular network (TIN) provides a versatile and widely used approach to representing terrain models in a way that retains the original sample points, adapts to variation in data density and incorporates linear features corresponding to natural or man-made phenomena. Classification of the scale-related priority of the constituent points and linear features can be used to create hierarchical, multiresolution TIN representations. A large proportion of the data items included in conventional and hierarchical TIN data structures are concerned with recording the topology of the triangulation. Although TINs typically use many fewer points then the main alternative representation of regular rectangular grids, they do not usually occupy much less data storage, due to the topological data. This paper describes a novel multiresolution storage scheme which uses an approach termed the Implicit TIN, in which storage requirements are reduced significantly by storing only the vertices and constraining features. TIN topology is reconstructed by a procedure when required. The Implicit TIN storage scheme has been demonstrated in the context of an experimental multiscale database. Variable-scale access is provided to polygonal regions of a terrain model which includes polygon, line and point objects that constrain the constructed triangulated model.

Multiresolution data structures provide a means of retrieving geographical features from a database at levels of detail which are adaptable to different scales of representation. A database design is presented which integrates multi-scale storage of point, linear and polygonal features, based on the line generalization tree, with a multi-scale surface model based on the Delaunay pyramid. The constituent vertices of topologically-structured geographical features are thus distributed between the triangulated levels of a Delaunay pyramid in which triangle edges are constrained to follow those features at differing degrees of generalization. Efficient locational access is achieved by imposing a spatial index on each level of the pyramid.

Abstract Manual name placement is an extremely time consuming task and has been one of the most difficult aspects of the map production process to automate. It is complicated by the large number of rules required for the selection and placement of names. A hybrid Prolog/Fortrau rule‐based system is described for placing names on a variety of map types. It uses a set of Prolog primitives for spatial search and name placement operations. The Ordnance Survey's 1:625000 scale digital dataset has been used to illustrate the application of rules for the selection of labels as well as for controlling their size and orientation. The application to other types of maps and diagrams is also briefly described.

The accumulation of geological information in digital form, due to modern exploration methods, has introduced the possibility of applying geographical information system technology to the field of geology. To achieve the benefits in information management and in data analysis and interpretation, however, it will be necessary to develop spatial models and associated data structures which are specifically designed for working in three dimensions. Some progress in this direction has already been demonstrated, with the application of octree spatial subdivision techniques to the storage of uniform volume elements representing mineral properties. By imposing octree tessellations on more precisely-defined geometric data, such as triangulated surfaces and polygon line segments, it may now be possible to combine efficient spatial addressing with topologically-coded boundary representations of geological strata. The development of storage schemes capable of representing such geological boundary models at different scales poses a particular problem, a possible solution to which may be by means of hierarchical classification of the vertices of triangulated surfaces according to shape contribution.