Algebraic approach to spatial reasoning

Abstract

A simple, exemplary system is described that performs reasoning about the spatial relationships between members of a set of spatial objects. The main problem of interest is to make sound and complete inferences about the set of all spatial relationships that hold between the objects, given prior information about a subset of the relationships. The spatial inferences are formalized within the framework of relation algebra and procedurally implemented in terms of constraint satisfaction procedures. Although the approach is general, the particular example employs a new ‘complete’ set of topological relationships that have been published elsewhere. In particular, a relation algebra for these topological relations is developed and a computational implementation of this algebra is described. Systems with such reasoning capabilities have many applications in geographical analysis and could be usefully incorporated into geographical information systems and related systems.     

An iconic query language for topological relationships in GIS

Abstract

The study of query languages for spatial databases is an active research area. This paper describes a new spatial query language that uses a visual grammar to express topological relationships. It is supplemented by text and icons to handle other spatial and non-spatial queries. A graphical user interface is also developed to provide an interactive environment for composing the iconic query command. To test the language, the interface is implemented on a SUN 4 Workstation and linked to Ingres, a relational DBMS. Preliminary tests show that the iconic query language is more convenient for expressing spatial concepts than conventional textual languages. This is due mainly to the two-dimensionality of iconic languages in contrast with the linear nature of conventional languages.     

栅格空间中三维地学实体拓扑关系表达的K6N9-I模型

论述栅格空间中三维地学实体拓扑空间关系研究的理论基础和现实意义,基于数字拓扑理论定义了栅格实体的6邻域内部I6、6邻域边界B6和k阶6邻域E6k,并以此分别替换9-I模型中实体的内部I、边界B和外部E,形成一种适用于栅格空间三维实体拓扑关系描述和分析的新9-I模型,即k阶6邻9-I模型(K6N9-I)。以基于规则六面体表达的地学实体为研究对象,通过扩展关系数据库SQL形成空间关系查询语言,实现了栅格空间中三维地学实体拓扑关系的定性表示和定量计算。以若干地学实体为例进行了初步实验,表明该模型实用方便,且在复杂地学实体的度量、方位等空间关系研究方面亦有较好的应用前景。     

Deferred decentralized movement pattern mining for geosensor networks

This article presents an algorithm for decentralized (in-network) data mining of the movement pattern flock among mobile geosensor nodes. The algorithm DDIG (Deferred Decentralized Information Grazing) allows roaming sensor nodes to ‘graze’ over time more information than they could access through their spatially limited perception range alone. The algorithm requires an intrinsic temporal deferral for pattern mining, as sensor nodes must be enabled to collect, memorize, exchange, and integrate their own and their neighbors' most current movement history before reasoning about patterns. A first set of experiments with trajectories of simulated agents showed that the algorithm accuracy increases with growing deferral. A second set of experiments with trajectories of actual tracked livestock reveals some of the shortcomings of the conceptual flocking model underlying DDIG in the context of a smart farming application. Finally, the experiments underline the general conclusion that decentralization in spatial computing can result in imperfect, yet useful knowledge.     

A complete classification of spatial relations using the Voronoi-based nine-intersection model

In this article we show that the Voronoi-based nine-intersection (V9I) model proposed by Chen et al. (2001, A Voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 15 (3), 201–220) is more expressive than what has been believed before. Given any two spatial entities A and B, the V9I relation between A and B is represented as a 3 × 3 Boolean matrix. For each pair of types of spatial entities that is, points, lines, and regions, we first show that most Boolean matrices do not represent a V9I relation by using topological constraints and the definition of Voronoi regions. Then, we provide illustrations for all the remaining matrices. This guarantees that our method is sound and complete. In particular, we show that there are 18 V9I relations between two areas with connected interior, while there are only nine four-intersection relations. Our investigations also show that, unlike many other spatial relation models, V9I relations are context or shape sensitive. That is, the existence of other entities or the shape of the entities may affect the validity of certain relations.     

基于空间推理的巷道三维拓扑建立

基于空间关系和空间推理理论,结合MGIS领域的需求建立巷道三维拓扑网络模型,研究巷道三维空间关系推理的算法及业务逻辑实现;开发巷道三维拓扑自动生成系统,实现了巷道空间与属性数据管理、三维拓扑自动处理、多尺度成果输出及基于三维拓扑的路径查询,为基于巷道的通风、运输、避灾、多尺度变换等应用奠定了基础。     

Database design for a multi-scale spatial information system

Abstract

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.     

Spatiotemporal data model for network time geographic analysis in the era of big data

There has been a resurgence of interest in time geography studies due to emerging spatiotemporal big data in urban environments. However, the rapid increase in the volume, diversity, and intensity of spatiotemporal data poses a significant challenge with respect to the representation and computation of time geographic entities and relations in road networks. To address this challenge, a spatiotemporal data model is proposed in this article. The proposed spatiotemporal data model is based on a compressed linear reference (CLR) technique to transform network time geographic entities in three-dimensional (3D) (x, y, t) space to two-dimensional (2D) CLR space. Using the proposed spatiotemporal data model, network time geographic entities can be stored and managed in classical spatial databases. Efficient spatial operations and index structures can be directly utilized to implement spatiotemporal operations and queries for network time geographic entities in CLR space. To validate the proposed spatiotemporal data model, a prototype system is developed using existing 2D GIS techniques. A case study is performed using large-scale datasets of space-time paths and prisms. The case study indicates that the proposed spatiotemporal data model is effective and efficient for storing, managing, and querying large-scale datasets of network time geographic entities.     

A combinatorial data model for representing topological relations among 3D geographical features in micro‐spatial environments

This research is motivated by the need for 3D GIS data models that allow for 3D spatial query, analysis and visualization of the subunits and internal network structure of ‘micro‐spatial environments’ (the 3D spatial structure within buildings). It explores a new way of representing the topological relationships among 3D geographical features such as buildings and their internal partitions or subunits. The 3D topological data model is called the combinatorial data model (CDM). It is a logical data model that simplifies and abstracts the complex topological relationships among 3D features through a hierarchical network structure called the node‐relation structure (NRS). This logical network structure is abstracted by using the property of Poincaré duality. It is modelled and presented in the paper using graph‐theoretic formalisms. The model was implemented with real data for evaluating its effectiveness for performing 3D spatial queries and visualization.     

A spatial analytical perspective on geographical information systems

Abstract

The field of geographical information systems (GIS) is reviewed from the viewpoint of spatial analysis which is the key component of the familiar four-part model of input, storage, analysis and output Input is constrained by the limits of manual methods and problems of ambiguity in scanning. The potential for developments in output is seen to be limited to the query mode of GIS operation, and to depend on abandoning the cartographic model. Discussion of storage methods is organized around the raster versus vector debate and the need to represent two spatial dimensions in one. A taxonomy of GIS spatial analysis operations is presented together with a generic data model. Prospects for implementation are discussed and seen to depend on appropriate scales of organization in national and international academic research.     

Generic cumulative annular bucket histogram for spatial selectivity estimation of spatial database management system

Selectivity estimation is crucial to query optimizers in choosing an optimal execution plan in a given spatial query, and there has been a great deal of focus on how to achieve good selectivity estimation for finer spatial selection operators. Equally crucial to this is understanding how to produce an updated spatial histogram. With this in mind, we used a cumulative annular bucket histogram (AB histogram), which not only accurately estimates the selectivity of a spatial selection or a spatial join operation with finer operators but also provides an updated spatial histogram to estimate the selectivity of subsequent spatial operations in a multi-level spatial query plan. A basic unit of AB histogram stores the number of minimum bounding rectangles whose lower left points and upper right points are located in specific rectangular regions. According to the basic units of a cumulative AB histogram, we can find out the selectivity of a spatial selection with a number of different finer operators. When it comes to spatial join operations, a relationship between two cumulative AB histograms can be translated into a relationship between one histogram and numerous query windows from the other histogram. Furthermore, an updated cumulative AB histogram can be simultaneously built into the process of selectivity calculation, making it possible to achieve both selectivity and an updated histogram of spatial join; its implementation made in the optimizer facility (OPF) of INGRES9.2. To highlight the performance of a cumulative AB histogram, several experiments have been conducted, with results showing that the cumulative AB histogram not only supports the selectivity estimation of spatial selection and spatial join with ‘Disjoint’, ‘Intersect’, ‘Within’, ‘Contains’, ‘Crosses’ and ‘Overlap’ operators but also supports the generation of an updated histogram. This indicates that Ingres would do better to find a query plan with low-execution costs.     

Statistics-based outlier detection for wireless sensor networks

Wireless sensor network (WSN) applications require efficient, accurate and timely data analysis in order to facilitate (near) real-time critical decision-making and situation awareness. Accurate analysis and decision-making relies on the quality of WSN data as well as on the additional information and context. Raw observations collected from sensor nodes, however, may have low data quality and reliability due to limited WSN resources and harsh deployment environments. This article addresses the quality of WSN data focusing on outlier detection. These are defined as observations that do not conform to the expected behaviour of the data. The developed methodology is based on time-series analysis and geostatistics. Experiments with a real data set from the Swiss Alps showed that the developed methodology accurately detected outliers in WSN data taking advantage of their spatial and temporal correlations. It is concluded that the incorporation of tools for outlier detection in WSNs can be based on current statistical methodology. This provides a usable and important tool in a novel scientific field.     

Efficient methods for Isoline extraction from a TIN

Abstract

A data structure is presented to store a triangulated irregular network digital elevation model, from which isolines (contour lines) can be extracted very efficiently. If the network is based on n points, then for any elevation, the isolines can be obtained in O (logn + k) query time, where k is the number of line segments that form the isolines. This compares favourably with O(n) time by straightforward computation. When a structured representation of the isolines is needed, the same query time applies. For a fully topological representation (with adjacency), the query requires additional O(c log c) or O(c log logo) time, where c is the number of connected components of isolines. In all three cases, the required data structure has only linear size.     

Graph-assisted landscape monitoring

The structure of computational spatial analysis has mostly built on data lattices inherited from cartography, where visualization of information takes priority over analysis. In these framings, spatial relationships cannot easily be encoded into traditional data lattices. This hinders spatial analysis that emphasizes how interactions among spatial entities reflect mutual inter-relationships. This paper explores how graph theoretic principles can support spatiotemporal analysis by enabling assessment of spatial and temporal relationships in landscape monitoring.     

基于HBase的矢量空间数据存储与查询方法及其应用

研究了HBase存储机制,针对现有存储查询方法效率低等缺陷,设计了HBase矢量空间数据存储表模式,如行键、过滤列族、几何列族及非几何列族等,以MapReduce算法为基础改进了原有的区域查询方法,上述改进有效提高了HBase中矢量空间数据查询效率。以某地近100 a地质灾害数据进行实验,结果表明：设计的存储模型可行,查询算法与传统查询算法相比效率更高;由于MapReduce运行过程中的通信等原因,当数据量小于5万级时,算法优势并不明显;当数据量大于10万级时,算法查询时间低于原来的1/2,而数据量达到100万级时,算法查询时间仅为算法改进前查询时间的1/20。数据量越大,并行化处理优势越明显。     

Decentralized and coordinate-free computation of critical points and surface networks in a discretized scalar field

This article provides a decentralized and coordinate-free algorithm, called decentralized gradient field (DGraF), to identify critical points (peaks, pits, and passes) and the topological structure of the surface network connecting those critical points. Algorithms that can operate in the network without centralized control and without coordinates are important in emerging resource-constrained spatial computing environments, in particular geosensor networks. Our approach accounts for the discrepancies between finite granularity sensor data and the underlying continuous field, ignored by previous work. Empirical evaluation shows that our DGraF algorithm can improve the accuracy of critical points identification when compared with the current state-of-the-art decentralized algorithm and matches the accuracy of a centralized algorithm for peaks and pits. The DGraF algorithm is efficient, requiring O(n) overall communication complexity, where n is the number of nodes in the geosensor network. Further, empirical investigations of our algorithm across a range of simulations demonstrate improved load balance of DGraF when compared with an existing decentralized algorithm. Our investigation highlights a number of important issues for future research on the detection of holes and the monitoring of dynamic events in a field.     

城市计算视角下的空间粗糙关联规则方法研究

同位模式表示不同类型的实体在空间邻域内共同频繁出现的规律,是城市实体空间关联的主要表达形式,但不能挖掘出指定实体的空间关联,需要寻找新的计算方法。在城市计算的视角下,通过引入粗糙集研究城市空间关联问题发现：1）该方法能把复杂的地理空间关联问题转换成信息决策问题,在信息决策表中计算城市实体之间的空间关联等拓扑关系,计算过程和结果可以挖掘城市行业之间的空间集聚和关联问题。2）通过属性约简得到属性核可以把高维空间数据降维,找到影响空间关联的重要因子。3）该方法拓宽了城市计算的理论方法体系和粗糙集方法的行业应用。最后,通过Python爬取南宁市城市服务业数据,进行方法的验证,计算结果与成熟的Apriori算法结果,以及南宁市服务业空间关联实际情况基本一致,证明了粗糙空间关联方法的可行性和正确性。     

Modeling the scale dependences of topological relations between lines and regions induced by reduction of attributes

The scale dependences of topological relations are caused by the changes of spatial objects at different scales, which are induced by the reduction of attributes. Generally, the detailed partitions and multi-scale attributes are stored in spatial databases, while the coarse partitions are not. Consequently, the detailed topological relations can be computed and regarded as known information, while the coarse relations stay unknown. However, many applications (e.g., multi-scale spatial data query) need to deal with the topological relations at multiple scales. In this study new methods are proposed to model and derive the scale dependences of topological relations between lines and multi-scale region partitions. The scale dependences of topological relations are modeled and used to derive the relations between lines and coarse partitions from the relations about the detailed partitions. The derivation can be performed in two steps. At the first step, the topological dependences between a line and two meeting, covered and contained regions are computed and stored into composition tables, respectively. At the second step, a graph is used to represent the neighboring relations among the regions in a detailed partition. The scale dependences and detailed relations are then used to derive topological relations at the coarse level. Our methods can also be extended to handle the scale dependences of relations about disconnected regions, or the combinations of connected and disconnected regions. Because our methods use the scale dependences to derive relations at the coarse level, rather than generating coarse partition and computing the relations with geometric information, they are more efficient to support scale-dependent applications.     

A generic model for planar geographical objects

Abstract

The lack of a coherent theory underpinning geographical databases is a serious obstacle to research efforts in this field. This article attempts to construct part of such a theory, namely the formalization of the underlying object mode for geographical data whose spatial references are embedded in the plane. Questions of approximation and error analysis, while exposed and briefly discussed here, do not form a major part of the discussion. This work extends earlier work by giving a detailed construction of the classes and operations for spatial objects embedded in the plane. It goes on to provide an explicit link between this object model and its representation in computationally meaningful terms using classes of simplicial complexes and operations acting upon these classes.     

Why not SQL!

Abstract

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.