基于R树的方向关系查询处理

方向关系描述了对象间的空间顺序关系.近年来,方向关系查询处理逐渐受到空间数据挖掘和地理信息系统等空间数据库应用领域研究者的关注.方向关系查询处理需要执行方向连接操作,目前有关空间连接的研究主要集中在拓扑关系和距离关系方面,而较少考虑方向关系.研究了基于R树的方向关系查询处理方法,定义了四元组模型表示对象MBR间的方向关系,提出了基于R树的处理方向关系查询过滤(filter)步骤的方法,并将提炼(refinement)步骤细化为3种不同的操作.所提出的方法能够高效处理任意对象间的方向关系查询.考虑到空间数据挖掘中方向关系查询通常是在满足一定距离约束条件的对象之间进行,还提出了一种同时利用方向和距离约束限制R树搜索空间的查询处理算法.实验证明,与不利用R树的方向关系查询处理方法相比,所提出的方法在I/O开销和CPU开销两方面都具有很高的性能.     

基于地址转发表的交换式以太网拓扑发现方法

提出一种称为连接推理技术(connections reasoning technique)的谓词逻辑推理方法推导节点间的连接关系.该方法把交换机地址转发表翻译为一组谓词公式,把拓扑发现问题转变为一个谓词逻辑推理的数学问题,借助数学工具对拓扑发现问题进行研究.基于连接推理技术提出了一种拓扑发现算法,与现有方法相比:(1)该方法能够更充分地利用不完整地址转发表的冗余信息,只需一小部分转发表就可以把整个网络拓扑构建出来;(2)该方法完全适用于多子网交换域的拓扑发现.此外,还提出了一种开销很小的动态网络拓扑发现方法.该算法成功地应用在社区宽带综合业务网络管理系统中.     

多路R树连接的加权处理

空间连接运算是空间数据查询中最重要、最耗时的基本操作之一,其中基于R树的空间连接(RJ)被认为是一种高效的处理机制,但在空间连接的精化阶段处理复杂的空间数据时需要很大的系统开销。基于MBR及直接查询谓词,提出了一种加权处理方法,并扩展了R树结构及MRJ算法。从而优化了多路R树连接的筛选处理,能得到更加有效的候选集;同时,减少了磁盘访问次数,可节省CPU及I/O的时间开销。还通过应用实例验证了其在空间数据库查询优化方面的优势。     

基于资源描述框架图切分与顶点选择性的高效子图匹配方法

在SPARQL查询过程中，含有复杂结构的资源描述框架（RDF）图的查询效率低下。为此，通过分析几种RDF图的基本结构与RDF顶点的选择性，提出RDF三元组模式选择性（RTPS）——一种基于RDF顶点选择性的图结构切分规则，以提高面向RDF图的子图匹配效率。首先，根据谓词结构在数据图与查询图中的通性建立RDF相邻谓词路径（RAPP）索引，将数据图结构转化为传入-传出双向谓词路径结构以确定查询顶点的搜索空间，并加快顶点的过滤；接着，通过整数线性规划（ILP）问题计算建模将复杂RDF查询图结构分解为若干结构简单的查询子图，通过分析RDF顶点在查询图中的相邻子图结构与特征，确立查询顶点的选择性以确定最优切分方式；然后，通过RDF顶点选择性与相邻子图的结构特征来缩小查询顶点的搜索空间范围，并在数据图中找到符合条件的RDF顶点；最后，遍历数据图以找到与查询子图结构相匹配的子图结构，将得到的子图进行连接并将其作为查询结果输出。实验采用控制变量法，比较了RTPS、RDF子图匹配（RSM）、RDF-3X、GraSS与R3F的查询响应时间。实验结果充分表明，与其他4种方法相比，当查询图复杂度高于9时，RTPS的查询响应时间更短，具有更高的查询效率。     

空间结构化查询语言-G/SQL

传统的地理信息系统对空间数据的处理是过程化的,并且不能将空间数据作为一个整体来对待。这种处理方法限制了空间数据应用的发展。空间结构化查询语言扩展了关系数据库的ＳＱＬ语言,朝着结构化的空间数据统一处理迈出了重要的一步。该文讨论了空间结构化查询语言的理论,在ＯＧＩＳ的概念和数据模型之上,提出了一套创新的地理数据模型,采用统一的方法存储和管理空间数据库中的属性数据和几何数据。根据这个模型,实现了一种空间结构化查询语言——Ｇ／ＳＱＬ。Ｇ／ＳＱＬ通过研究地物关系的９－交叉模型确定面向空间数据的扩充的空间算子,为应用程序提供空间拓扑关系谓词和空间函数。应用Ｇ／ＳＱＬ成功地开发了一个基于Ｗｅｂ 的地理信息应用系统ＷｅｂＧＩＳ。实践表明,Ｇ／ＳＱＬ提供的空间关系谓词和空间函数完备而且易于使用。还给出了Ｇ／ＳＱＬ语法的ＢＮＦ表示。     

一种模糊区域的拓扑关系模型

空间区域拓扑关系建模是空间推理、地理信息系统(GIS)和计算机视觉等领域一个非常重要的主题，模糊区域的拓扑关系建模正日益受到相关领域研究者的重视，在分析现有模型的基础上，提出了一种模糊区域的拓扑关系模型，该模型利用模糊集来表示模糊区域，通过三个谓词的真值来判断区域间的拓扑关系，将分明区域作为特例统一处理，根据谓词的多种真值能够实现多层次上的拓扑关系分析．     

拓扑服务中融合GIS与拓扑发现技术的研究

传统的网络拓扑服务通过拓扑发现技术,描述了网络节点间的逻辑连接关系,基于GIS技术的网络拓扑服务,则体现了网络传输线路、网络节点间的空间连接关系。对这二种网络拓扑服务的实现展开研究,提出一种将两者相融合的方法,将网络资源及其拓扑关系视图化,以便于网络资源的保存、查询、管理,在计算机上实现准确真实的空间分析和可视化表达,实现了两者的优势互补,为网络资源利用,故障检测、定位、修复提供一种全新、强大的辅助工具。     

一种并行多路空间连接处理方法

空间连接查询是最耗时,最重要的空间查询、空间多路连接是涉及多个空间关系的连接查询,顺序空间连接查询的效率还是不能令人满意,研究利用并行机制提高空间连接查询效率成为有吸引力的方向,并行空间连接处理由三个阶段组成;任务创建,任务分配和任务并行执行,本文提出一种新的平面扫描方法用于多路并行处理的任务创建过程,随机提出基于花费估计的动态任务分配策略,给出了花费模型,并将其推到处理多路并行连接查询处理以实现负荷平衡。     

基于RDF图结构切分的高效子图匹配方法

针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架（RDF）图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。     

分布式空间数据分片与跨边界拓扑连接优化方法

研究分布式空间数据库(distributed spatial database,简称DSDB)中数据按区域分片时的跨边界片段拓扑连接查询问题,并提出相应的优化方法.首先研究了分布式环境下的空间数据的分片与分布,提出了空间数据分片的扩展原则:空间聚集性、空间对象的不分割性、逻辑无缝保持性.然后,将区域分割分片环境下的片段连接分为跨边界和非跨边界两类;同时,将拓扑关系分为两类,重点研究跨边界的两类片段拓扑连接.提出了跨边界空间片段拓扑连接优化的两个定理,并给出了证明.以此为基础,给出了跨边界空间拓扑连接优化规则,包括连接去除规则和连接优化转化规则.最后设计了详细的实验,对自然连接策略、半连接策略以及所提出的连接策略进行效率比较,结果表明,所提出的方法对跨边界连接优化有明显优势.因此,所提出的理论和方法可以用于分布式跨边界拓扑关系查询的优化.     

一种基于关键词搜索的空间连接查询

许多实际的应用需要同时支持空间连接查询和关键词搜索。在给出基于关键词的空间连接（KSJ）查询定义的基础上,对参与KSJ查询的空间数据集建立MIR2-树索引结构,并结合一些高效的搜索剪枝策略,提出一种基于宽度优先的KSJ查询算法。实验结果表明该算法可有效支持基于关键词的空间连接查询处理。     

Modelling topological spatial relations: Strategies for query processing

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.     

基于结点度和欧拉数的拓扑关系一般化描述

拓扑关系是GIS中空间目标间最基本、最重要的关系之一,然而目前的拓扑关系模型在描述两目标间的详细拓扑关系方面存在不足。针对二元目标间任意交的情况,提出了基于结点度和欧拉数的拓扑关系模型的一般化描述形式,使用目标整体间交(∩)、差(\\)两个集合算子的结果来区分目标间的拓扑关系,结果的取值包括内容、维数、结点度、欧拉数4个拓扑不变量。重点讨论了线/线、线/面和面/面拓扑关系一般化描述表达式。     

基于弱水印的地理数据拓扑完整性检验方法

拓扑关系是空间关系研究的基础问题,被广泛应用在空间查询和空间推理等方面。为了检测地理数据拓扑关系的完整性,提出了一种基于弱水印的地理数据拓扑完整性检验方法。通过地物之间空间相离距离生成水印信息,并修改其相离距离比值,根据比值进行地物缩放以达到嵌入水印的目的。在水印检测时,根据生成的水印与提取的水印的匹配结果来判定地理数据的拓扑完整性。实验结果表明,本方法可以有效地检测出矢量地理数据的拓扑完整性。     

支持关键词搜索的空间连接查询研究

近年来,许多实际应用不仅需要支持空间连接查询而且需要具备关键词搜索功能,以帮助用户查找那些既满足空间连接条件又包含指定关键词的空间对象组合.正是在这种需求的驱动之下,定义了一种具备关键词搜索功能的空间连接查询(Spatial Join with Keyword Search,缩写SJKS),并提出了一种基于IR2-Tree的SJKS查询处理算法(IR2-TreeSJKS算法),旨在实现关键词搜索与空间连接查询的高效结合.实验表明,本算法可有效支持具有关键词搜索功能的空间连接查询处理.     

基于空间数据引擎的数据库设计与构建

空间数据可通过矢量数据和栅格数据两种数据结构来表达,并可利用ArcSDE对这2种数据进行管理。该文以ArcSDE为空间数据引擎,用大型关系数据库管理空间数据,建立了数据库、服务器、客户端3层体系结构。以C/S和B/S相结合方式运行的网络化海量数据库管理系统,实现了空间数据的有效组织和管理,并在实践中得到了很好的应用。     

Representing topological relationships among heterogeneous Geometry-Collection features

Topological relationships between two spatial features represent important knowledge in Geograph-ical Information Systems (GIS). In the last few years, many models that represent topological relationships havebeen proposed. But these models cannot represent the topological relationships between heterogeneous geome-trycollection features, which are composed of different dimensional geometries. In this paper, the formal definitionof regular heterogeneous geometrycollection and regularization rules are given. Based on the spatial model, twomethods for representing topological relationships between these complex features are proposed. The first methodis Dimensionally Extended Nine-Intersection Model Based on Components (DE-9IMBC) that extends Dimension-ally Extended Nine-Intersection Model (DE-9IM) and takes into account the topological relationships betweencomponents of these complex features. The advantage of DE-9IMBC is that a large number of different topo-logical relationships can be checked. The secon     

基于Kd树递归区域划分的分布式空间连接查询

随着空间信息应用需求的不断增长,分布式空间查询处理已经成为空间数据库领域一个重要的研究问题,其中应用最广也是最复杂的一类查询是分布式空间连接查询,分布式空间连接操作的计算代价与传输代价都非常高。目前处理该问题的策略大都要求空间数据集上存在索引并且对数据分布敏感,然而在某些情况下,这个前提并不存在。面对这个问题,本文提出一种基于Kd树递归区域划分的分布式空间连接策略,该策略以最小化网络数据传输代价为目标,基于任务分治的思想对连接区域进行递归划分。实验表明,该策略在不同数据分布情况下均优于传统查询策略,能有效地减小网络传输代价,表现出较好的性能。     

基于R树的空间查询连接处理优化与实现

空间索引作为空间数据库的关键技术,其性能的高低决定着整个空间数据库的效率。通过对现有的多种空间索引结构进行比较分析,基于开源数据库Ingres实现了广度优先R树连接算法(BFRJ),并对其进行了局部优化和全局优化。基于真实数据的实验结果分析,证实了采用适当的全局优化方法的BFRJ优于其他已知的空间连接算法方法。