VASA: An algebra for vague spatial data in databases

Many geographical applications deal with objects in space that cannot be adequately described by determinate, crisp spatial concepts because of their intrinsically indeterminate and vague nature. Geographical information systems and spatial database systems are currently unable to cope with this kind of data. To support the efficient representation, querying, and manipulation of vague spatial data in a database context, we present a formal data model called vague spatial algebra (VASA). This algebra comprises a set of vague spatial data types for vague points, vague lines, and vague regions together with a comprehensive collection of vague spatial operations and vague topological predicates. One of VASA's main benefits is that its formal framework is based on well known, general, and exact models of crisp spatial data types. This enables an exact definition of the vague spatial model since we can build upon an already existing theory of spatial data types. In particular, crisp spatial data types turn out to be a special case of their vague counterparts. In addition, our approach enables executable specifications for the operations, which can be immediately used as implementations. The article offers a precise and conceptually clean foundation for implementing a DBMS extension for vague spatial data and demonstrates the embedding of these new data types as attribute data types in a database schema as well as the incorporation of vague spatial operations and predicates into queries formulated in an SQL-like query language. All concepts have been verified in a prototype implementation.     

Realm-based spatial data types: The ROSE algebra

Spatial data types or algebras for database systems should (1) be fully general, that is, closed under set operations, (2) have formally defined semantics, (3) be defined in terms of finite representations available in computers, (4) offer facilities to enforce geometric consistency of related spatial objects, and (5) be independent of a particular DBMS data model, but cooperate with any. We present an algebra that usesrealms as geometric domains underlying spatial data types. A realm, as a general database concept, is a finite, dynamic, user-defined structure underlying one or more system data types. Problems of numerical robustness and topological correctness are solved within and below the realm layer so that spatial algebras defined above a realm have very nice algebraic properties. Realms also interact with a DMBS to enforce geometric consistency on object creation or update. The ROSE algebra is defined on top of realms and offers general types to represent point, line, and region features, together with a comprehensive set of operations. It is described within a polymorphic type system and interacts with a DMBS data model and query language through an abstractobject model interface. An example integration of ROSE into the object-oriented data model O₂ and its query language is presented.     

不确定性空间关系

空间关系在空间查询语言、基于内容的数据检索及空间分析中有重要作用。不确定性是空间关系的固有特性，但至今没有受到研究人员的足够重视。为了使人们对该理论有个概略了解，首先给出了空间关系不确定性的定义、内涵及其对空间关系应用的影响；然后从数据的不确定性、认知的不确定性以及空间关系分析处理的不确定性等3个方面详细地分析了空间关系不确定性的来源，同时提出了空间关系不确定性的处理方式，并以空间关系不确定性的3个来源为标准，评价并指出了定性空间关系表达方法的不足之处；最后，给出了用模糊集方法研究模糊空间关系的框架和主要内容，以便为不确定性空间关系的研究奠定基础。     

基于几何元素的城市三维地理信息系统空间数据模型

空间数据模型是城市三维地理信息系统建立的核心问题。基于不同的城市空间对象划分方法,提出了城市三维地理信息系统的十八个空间数据模型:把空间现象抽象为六类对象:点对象、线对象、规则面对象、规则体对象、不规则对象和DTM,基于六种几何元素(点、直线段、多边形、函数构造面、TIN面片、规则体素)的不同组合,提出了城市三维地理信息系统的九个空间数据模型;把空间现象抽象为五类对象:0维空间对象(点对象)、一维空间对象(线对象)、二维空间对象(面对象)、三维空间对象(体对象)和DTM,基于六种几何元素的不同组合提出了八个空间数据模型;把空间现象抽象为0维对象(点对象)、一维对象(线对象)、二维对象(面对象)、三维对象(体对象)、DTM,基于点、直线段、TIN面片、多边形、规则面、不规则面六类几何元素提出了一个空间数据模型。通过对一个数据模型的实验验证和各模型的理论分析,表明了模型的特点及可行性。     

Spatial query processing for fuzzy objects

Range and nearest neighbor queries are the most common types of spatial queries, which have been investigated extensively in the last decades due to its broad range of applications. In this paper, we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS communities. Existing research on fuzzy objects mainly focuses on modeling basic fuzzy object types and operations, leaving the processing of more advanced queries largely untouched. In this paper, we propose two new kinds of spatial queries for fuzzy objects, namely single threshold query and continuous threshold query, to determine the query results which qualify at a certain probability threshold and within a probability interval, respectively. For efficient single threshold query processing, we optimize the classical R-tree-based search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To enhance the performance of continuous threshold queries, effective pruning rules are developed to reduce the search space and speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques is verified with an extensive set of experiments using both synthetic and real datasets.     

The data type of spatial objects

A spatial object consists of data assigned to points in a space. Spatial objects, such as memory states and three dimensional graphical scenes, are diverse and ubiquitous in computing. We develop a general theory of spatial objects by modelling abstract data types of spatial objects as topological algebras of functions. One useful algebra is that of continuous functions, with operations derived from operations on space and data, and equipped with the compact-open topology. Terms are used as abstract syntax for defining spatial objects and conditional equational specifications are used for reasoning. We pose a completeness problem: Given a selection of operations on spatial objects, do the terms approximate all the spatial objects to arbitrary accuracy? We give some general methods for solving the problem and consider their application to spatial objects with real number attributes.     

基于Oracle Spatial的ITS空间数据库的实现及访问

在智能交通系统(Intelligent Transportatlon System，ITS)中，空间数据库的实现和访问至关重要。随着ITS的发展，基于传统的纯关系型数据库设计的空间数据库系统，其属性数据和空间数据是分开存储的，难以满足新型ITS在内容、数量、类型、关系等方面高速增长的要求。为此一些数据库厂商对传统的关系型数据库技术进行了扩充，并推出了一序列新的数据库产品，如Oracle公司的Oracle8i，真正实现了属性数据和空间数据统一存储和管理。该文结合实际ITS信息系统开发，分析了Oracle8i的数据库技术——Oracle Spatial，提出了一种基于Orackle Spatial的ITS空间数据库的实现及访问方法。     

Spatial Data Mining: Database Primitives, Algorithms and Efficient DBMS Support

Spatial data mining algorithms heavily depend on the efficient processing of neighborhood relations since the neighbors of many objects have to be investigated in a single run of a typical algorithm. Therefore, providing general concepts for neighborhood relations as well as an efficient implementation of these concepts will allow a tight integration of spatial data mining algorithms with a spatial database management system. This will speed up both, the development and the execution of spatial data mining algorithms. In this paper, we define neighborhood graphs and paths and a small set of database primitives for their manipulation. We show that typical spatial data mining algorithms are well supported by the proposed basic operations. For finding significant spatial patterns, only certain classes of paths “leading away” from a starting object are relevant. We discuss filters allowing only such neighborhood paths which will significantly reduce the search space for spatial data mining algorithms. Furthermore, we introduce neighborhood indices to speed up the processing of our database primitives. We implemented the database primitives on top of a commercial spatial database management system. The effectiveness and efficiency of the proposed approach was evaluated by using an analytical cost model and an extensive experimental study on a geographic database.     

Enhancing accuracy and expressive power of range query answers over incomplete spatial databases via a novel reasoning approach

Modern spatial database applications built on top of distributed and heterogeneous spatial information sources such as conventional spatial databases underlying Geographical Information Systems (GIS), spatial data files and spatial information acquired or inferred from the Web, suffer from data integration and topological consistency problems. This more-and-more conveys in incomplete information, which makes answering range queries over incomplete spatial databases a leading research challenge in spatial database systems research. A significant instance of this setting is represented by the application scenario in which the geometrical information on a sub-set of spatial database objects is incomplete whereas the spatial database still stores topological relations among these objects (e.g., containment relations). Focusing on the spatial database application scenario above, in this paper we propose and experimentally assess a novel technique for efficiently answering range queries over incomplete spatial databases via integrating geometrical information and topological reasoning. We also propose I-SQE (Spatial Query Engine for Incomplete Information), an innovative query engine implementing this technique. Our proposed technique results not only effective but also efficient against both synthetic and real-life spatial data sets, and it finally allows us to enhance the quality and the expressive power of retrieved answers by meaningfully taking advantages from the amenity of representing spatial database objects via both the geometrical and the topological level.     

A fully spatial personalized differentially private mechanism to provide non-uniform privacy guarantees for spatial databases

Spatial databases are essential to applications in a wide variety of domains. One of the main privacy concerns when answering statistical queries, such as range counting queries, over a spatial database is that an adversary observing changes in query answers may be able to determine whether or not a particular geometric object is present in the database. Differential privacy addresses this concern by guaranteeing that the presence or absence of a geometric object has little effect on query answers. Most of the current differentially private mechanisms for spatial databases ignore the fact that privacy is personal and, thus, provide the same privacy protection for all geometric objects. However, some particular geometric objects may be more sensitive to privacy issues than others, requiring stronger differential privacy guarantees. In this paper, we introduce the concept of spatial personalized differential privacy for spatial databases where different geometric objects have different privacy protection requirements. Also, we present SPDP-PCE, a novel spatial personalized differentially private mechanism to answer range counting queries over spatial databases that fully considers the privacy protection requirements of geometric objects in the underlying geometric space in both steps of noise addition and consistency enforcement. Our experimental results on real datasets demonstrate the effectiveness of SPDP-PCE under various total privacy budgets, query shapes, and privacy level distributions.     

The Farthest Spatial Skyline Queries

Pareto-optimal objects are favored as each of such objects has at least one competitive edge against all other objects, or “not dominated”. Recently, in the database literature, skyline queries have gained attention as an effective way to identify such pareto-optimal objects. In particular, this paper studies the pareto-optimal objects in perspective of facility or business locations. More specifically, given data points P and query points Q in two-dimensional space, our goal is to retrieve data points that are farther from at least one query point than all the other data points. Such queries are helpful in identifying spatial locations far away from undesirable locations, e.g., unpleasant facilities or business competitors. To solve this problem, we first study a baseline Algorithm TFSS and propose an efficient progressive Algorithm BBFS, which significantly outperforms TFSS by exploiting spatial locality. We also develop an efficient approximation algorithm to trade accuracy for efficiency. We validate our proposed algorithms using extensive evaluations over synthetic and real datasets.     

一种基于空间邻接关系的k-means聚类改进算法

空间对象不仅具有非空间的属性特征，而且具有与空间位置、拓扑结构相关的空间特征。利用传统的聚类方法对空间对象进行聚类时，由于没有考虑空间关系，同一类的对象可能出现在空间不相邻的位置。基于空间邻接关系的k-means改进算法将相邻对象的空间邻接关系作为约束条件加以考虑，使聚类结果既反映了属性特征的相似程度，又反映了对象的空间相邻状态，从而可以揭示不同类别对象的空间分布格局，因此其比传统的k-means方法更适合于空间对象的聚类分析。     

Efficient Implementation Techniques for Topological Predicates on Complex Spatial Objects

Topological relationships like overlap, inside, meet, and disjoint uniquely characterize the relative position between objects in space. For a long time, they have been a focus of interdisciplinary research as in artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates, they support the design of suitable query languages for spatial data retrieval and analysis in spatial database systems and geographical information systems. While, to a large extent, conceptual aspects of topological predicates (like their definition and reasoning with them) as well as strategies for avoiding unnecessary or repetitive predicate executions (like predicate migration and spatial index structures) have been emphasized, the development of robust and efficient implementation techniques for them has been largely neglected. Especially the recent design of topological predicates for all combinations of complex spatial data types has resulted in a large increase of their numbers and stressed the importance of their efficient implementation. The goal of this article is to develop correct and efficient implementation techniques of topological predicates for all combinations of complex spatial data types including two-dimensional point, line, and region objects, as they have been specified by different authors and in different commercial and public domain software packages. Our solution consists of two phases. In the exploration phase, for a given scene of two spatial objects, all topological events like intersection and meeting situations are summarized in two precisely defined topological feature vectors (one for each argument object of a topological predicate) whose specifications are characteristic and unique for each combination of spatial data types. These vectors serve as input for the evaluation phase which analyzes the topological events and determines the Boolean result of a topological predicate (predicate verification) or the kind of topological predicate (predicate determination) by a formally defined method called nine-intersection matrix characterization. Besides this general evaluation method, the article presents an optimized method for predicate verification, called matrix thinning, and an optimized method for predicate determination, called minimum cost decision tree. The methods presented in this article are applicable to all known complete collections of mutually exclusive topological predicates that are formally based on the well known nine-intersection model.

基于Oracle Spatial的税收征管空间数据库的设计与实现

传统税收征管信息系统普遍存在空间数据利用率低、空间数据与属性数据单独存储、空间数据存储和访问的效率较低等问题。采用Oracle Spatial可以有效地组织空间数据和属性数据,并对两者进行统一管理,有效地提高了空间数据的存储和查询效率,并为税收征管WebGIS系统的建立奠定了基础。本文介绍了Oracle Spatial的运行机制与原理,详细阐述了基于Oracle Spatial的税收空间数据库(TAXSDB)的设计和实现过程,并提出了TAXSDB的优化策略。     

Modeling and measuring the spatial relation “along”: Regions,contours and fuzzy sets

The analysis of spatial relations among objects in an image is an important vision problem that involves both shape analysis and structural pattern recognition. In this paper, we propose a new approach to characterize the spatial relation along, an important feature of spatial configurations in space that has been overlooked in the literature up to now. We propose a mathematical definition of the degree to which an object A is along an object B, based on the region between A and B and a degree of elongatedness of this region. In order to better fit the perceptual meaning of the relation, distance information is included as well. In order to cover a more wide range of potential applications, both the crisp and fuzzy cases are considered. In the crisp case, the objects are represented in terms of 2D regions or 1D contours, and the definition of the alongness between them is derived from a visibility notion and from the region between the objects. However, the computational complexity of this approach leads us to the proposition of a new model to calculate the between region using the convex hull of the contours. On the fuzzy side, the region-based approach is extended. Experimental results obtained using synthetic shapes and brain structures in medical imaging corroborate the proposed model and the derived measures of alongness, thus showing that they agree with the common sense.     

一种支持空间拓扑分析的3维数据模型

3维空间数据模型是构建3维空间数据库和3维GIS的基础，有着极为重要的研究意义。为了能更好地表示空间3维对象，提出了一种基于3D-realms的数据模型，它是对基于2D-realms的空间数据模型的3维扩展，并详细给出了该模型的基本定义、语义描述和基于该模型的3维空间对象操作，运用分层的方法可将该模型分为4层：3维几何原语层、3D-realms层、3维基本空间构建要素层和3维基本空间对象层（包括点、线、面和体）。其中，由于每个较低层都是构建较高层中元素的基础，因此可为上层提供支持。实验表明，基于3D-realms的3维空间数据模型不仅能保证拓扑关系的正确性，而且能较好地表示3维空间对象，并能有效地支持3维空间拓扑分析操作。     

空间索引技术-回顾与展望

空间数据库系统通过引入空间索引机制来提高空间数据操作的效率。迄今人们已经提出了许多空间索引方法,文章回顾了这些方法的基本思想,并根据它们所采用的基础数据结构和存储空间数据的方法将现有的空间索引方法进行分类。最后,简要的讨论了空间索引方法的发展方向。     

基于SDSS的空间数据库系统模型的研究

文章通过对现有GIS中空间数据库系统模型的分析与比较,提出了一个适用于智能化空间决策支持系统(SDSS)的空间数据库系统模型。在该数据库系统模型中,通过在数据库上附加一层中间件来解决从空间对象模型到数据库存贮的映射问题,从而较好地实现了空间数据和属性数据的统一管理。     

Robust spatial flood vulnerability assessment for Han River using fuzzy TOPSIS with α-cut level set

This study aims to improve the general flood vulnerability approach using fuzzy TOPSIS based on α-cut level sets which can reduce the uncertainty inherent in even fuzzy multi-criteria decision making process. Since fuzzy TOPSIS leads to a crisp closeness for each alternative, it is frequently argued that fuzzy weights and fuzzy ratings should be in fuzzy relative closeness. Therefore, this study used a modified α-cut level set based fuzzy TOPSIS to develop a spatial flood vulnerability approach for Han River in Korea, considering various uncertainties in weights derivation and crisp data aggregation. Two results from fuzzy TOPSIS and modified fuzzy TOPSIS were compared. Some regions which showed no or small ranking changes have their centro-symmetric distributions, while other regions whose rankings varied dynamically, have biased (anti-symmetric) distributions. It can be concluded that α-cut level set based fuzzy TOPSIS produce more robust prioritization since more uncertainties can be considered. This method can be applied to robust spatial vulnerability or decision making in water resources management.     

空间对象的几何表示

1 引言空间推理是指利用空间理论和人工智能技术对空间对象建模、描述和表示,并据此对空间对象间的空间关系进行的定性或定量的分析和处理过程。目前,空间推理被广泛应用于地理信息系统、机器人导航、高级视觉、自然语言理解、工程设计和物理位置的常识推理等,是人工智能领域的一个研究热点。