查询计划枚举中的空间启发式规则研究

在查询计划枚举空间巨大的情况下,空间启发式规则对排除一些不可行或低效的查询计划、提高系统的执行效率有重要意义。本文基于空间等价类、空间约束对的概念,提出了空间连接应建立在空间等价类或空间约束对上的启发式规则,构建了查询计划树中各类连接关系的放置规则以及空间等价类的连接递推规则,提出了空间索引替换表以及空间索引的若干放置规则。论文阐述了如何尽可能用低代价的空间操作,尽早过滤出较少的数据结果,降低参与后续运算的数据量,提高系统查询效率。最后,以空间查询案例为例,展示了这些规则在缩小枚举空间方面的作用。     

分布式空间拓扑连接查询优化处理算法

针对传统分布式数据库查询应用于分布式空间数据库查询带来的传输和处理代价高的问题,本文结合已有分布式跨边界片段连接优化方法,深入研究了分布式空间拓扑连接查询处理,提出跨边界连接优化的空间查询优化算法,丰富了传统的分布式查询的关系代数等价变换规则。同时,针对不同片段连接类型的分布式空间查询全局优化策略,实现了分布式空间查询分解与数据本地化,从而优化分布式查询中的数据传输所付出的高昂代价。最后,提出了结点归并、连接归并树、执行结点、执行计划树等分布式查询优化方法,利用相应归并和优化算法将全局空间查询转化为各个场地局部空间数据库的具体执行计划,消除分布式查询中的冗余计算,优化查询计算策略,从而解决分布式空间查询中的处理代价高的问题。通过分布式空间查询实验表明,本文的算法能够较好地提高分布式空间查询的性能。     

基于MPP架构的并行空间数据库原型系统的设计与实现

快速高效地查询信息是衡量当前空间数据库性能的重要指标之一。传统的单节点关系型空间数据管理方式难以满足大数据量空间数据查询的需求,特别是高性能的复杂空间多表连接任务需求。鉴此,本文设计并实现了基于Massive Parallel Processing（MPP）架构的并行空间数据库中间件原型系统。系统充分利用无共享（shared-nothing）架构的优势,特别是针对空间数据的特性,设计了并行空间数据划分与导入、并行空间多表连接、空间数据查询优化等算法与模型。首先介绍了近年来并行数据库系统的发展现状,接着阐述了基于MPP架构的并行空间数据库中间件系统的查询计划算法及其系统架构,最后作者对一些大规模数据量做查询实验及其查询结果分析。实验表明,在处理挖掘大规模数据量时,该系统有近似线性的加速比,相比于传统单节点数据库,它能充分提高海量空间数据的复杂查询的性能,解决了空间数据库并行化处理海量数据的问题。     

基于资源环境数据格网化表达的关联模式发现

传统空间关联模式以空间谓词作为发现逻辑进行知识发现,会导致关联模式侧重空间位置关联,并且挖掘结果受所建立谓词表的限制,存在所发现模式固定、解释自由度差等问题。本文提出一种不依赖于空间谓词的关联模式发现方法,该方法将空间数据进行格网化表达,对格网化结果以平滑移动的N×N掩膜进行多约束事务化,将传统Apriori算法去除属性自连接,然后对所构建的空间事务化数据库进行关联模式探索,抽取有价值的关联模式。最后,以山西省晋城市长河流域为实证研究区,建立煤、地、水空间事务数据库,给出格网化表达的定量误差,探索其隐含空间关联模式,并以同位模式验证了事务化结果的精度。格网化生成覆盖研究区的64 m格网28 434个,各数据层格网化误差均在5%以内,以耕地为主因子事务化结果共有记录38 310条记录。对抽取的部分关联模式分析表明：发现结果符合长河流域矿农复合区背景下耕地相关的先验知识;该方法能有效提取空间数据及其属性信息中潜在的关联模式,提高了挖掘过程自由度和结果的兴趣度。     

基于拓扑谓词的空间拓扑关系相似性度量模型与应用

空间拓扑关系相似性度量是空间数据相似性度量的重要组成部分,它是空间数据检索和空间场景相似查询的基础和关键。本文旨在建立一种能够同时度量简单和复杂拓扑关系间的相似性度量模型。首先,以9个拓扑谓词提出一种简单拓扑关系间相似性度量方法,即定义简单拓扑关系之间距离为两个9交集矩阵之间的距离,从而得到简单拓扑关系之间的相似度。然后,综合考虑实体集合间的数量相似度和维数相似度,建立实体集合间的简单拓扑关系相似性度量模型,并在上述实体集合间简单拓扑关系相似性度量的基础上,采用分解-组合的策略先将复杂拓扑关系分解为若干个局部拓扑关系,通过组合局部拓扑关系之间的相似度,直至建立复杂拓扑关系间的相似性度量模型。实验表明,制图综合中的选取对空间实体集合之间拓扑关系相似度的影响最大,其他因素影响较小,因此,其能以拓扑关系相似度来度量制图综合对拓扑关系的改变程度。     

一种自然邻近关系查询的空间索引结构

自然邻近关系在空间数据库管理系统中具有十分重要的地位。为了克服Voronoi图受空间目标位置的影响,本文采用约束Delaunay三角网,针对在二维欧式空间中离散面目标的自然邻近关系查询问题。首先对离散面进行三角剖分,然后将代表相同邻近关系的三角形合并成一个union,进而建立面目标自然邻近关系表达结构-Unions Delaunay。通过与Unions Delaunay相结合建立空间索引结构-R-tree Gridfile来实现对空间目标自然邻居完备的候选集提取以及索引结构的更新。对比实验结果表明R-tree Gridfile索引结构能够有效支持空间目标的自然邻近关系查询。     

基于MST聚类的空间数据离群挖掘算法

空间离群是指空间邻域中属性特征值明显不同于其他对象的空间对象,空间数据离群挖掘能为人们提供很多有趣的信息,但空间数据具有复杂的拓扑关系、方位关系和度量关系等空间特征,传统的面向事务型数据库的离群挖掘算法并不适用于空间数据库。本文提出了基于MST(Minimum Spanning Tree,最小生成树)聚类的空间数据离群挖掘算法(SOM);有机结合了最小生成树理论与密度的方法,既体现了空间离群的局部特性,又体现了空间离群的孤立程度。该算法通过MST维护空间数据的基本空间结构特征,通过打断MST中最不一致的边形成MST聚类,不仅具有密度的聚类方法能够聚集非球状簇和分布不均的数据集的特点,而且聚类结果不依赖于用户参数的选择,因此,离群挖掘结果更合理。最后,通过实例数据,验证了该算法的有效性,它适用于大规模空间数据集的离群挖掘。     

基于OO4O和Visual C++6.0实现Oracle9i Spatial中空间数据的操作

从OracleSpatial9i管理空间数据的优良特性出发,利用Oracle的OLE对象OO4O和VisualC 6.0的集成实现了对Oracle数据库中空间对象的读取和存储,以及空间对象拓扑关系和空间对象的查询,因此对深入研究基于OracleSpatial空间数据的管理方法有一定的指导作用。     

空间数据访问集成与分布式空间数据源对象查询

目前,针对空间数据库的访问与处理方法,无法满足分布式环境下异构数据源的服务化存取和面向空间数据源的对象查询处理需求。本文给出了数据网格环境下的分布式空间数据访问与查询的方法和实现,并在服务化查询处理过程中,嵌入符合SQL/MM查询规范的空间拓展函数,实现分布式空间数据对象查询和嵌入查询过程中的空间数据分析处理。在此基础上,给出空间数据对象查询树的构造过程,以及分布式空间查询工作流的执行流程。数据访问与集成策略在空间数据处理上的应用,对异构空间数据源协同处理等,涉及大规模空间数据存取访问的应用需求,有很好的理论和实际应用价值。     

基于Shark/Spark的分布式空间数据分析框架

随着空间数据的与日俱增,传统依托于单节点的空间数据管理方法,已难以满足海量数据高并发的需求。云计算的兴起带来机遇与挑战,分布式技术与数据库技术的优势互补,为云计算下高效的数据管理提供了可能。本文提出一种在分布式计算引擎（Shark/Spark）中集合之关键技术（包括空间数据映射、空间数据加载、数据备份及空间查询等）,将空间数据库对空间数据的高效存储、索引及查询优势与分布式计算引擎对复杂计算的优势相结合,实现一种基于Shark/Spark的分布式空间数据分析框架。在具体实现中,通过空间自定义函数和空间函数下推2种方式实现空间查询,结果表明,影响返回结果数据量的空间查询更适合下推给空间数据库完成,而不影响返回结果数据量的空间查询,利用分布式计算引擎直接运算更有优势。同时,通过与现有的一种分布式GIS方案（ArcGIS on Hadoop）对比发现,空间数据库的空间索引可有效提高查询效率,空间数据管理也更加独立。     

基于地理语义的空间关系查询和推理

地理空间中的地物,根据其本体类型具有不同的地理语义特征。受到地理语义的影响,人们在描述几何特征和关系相似的物体之间的空间关系时,所用的词汇是不同的。目前,人们在空间关系的自然语言查询方面的研究主要集中在空间关系描述、空间关系自然语言形式化表达、空间关系自然语言查询语句的转换,以及空间关系自然语言查询的查询接口等方面,没有考虑到地理本体的语义差异,这会使得空间关系的自然语言查询不能符合人类语言和认知的习惯。本文依据一些学者在空间关系的自然语言描述的形式化(主要是线和线、线和面等形状的空间地物之间的关系)研究的基础上,针对不同地理本体类型的空间地物和空间关系自然语言描述词汇之间对应的语义关系有所不同的特点,总结了自然语言词汇在描述空间关系时的对应规则,提出不同特征类型地物和描述词汇之间的规则库设计方法,并设计部分空间地物的规则实例。最后,结合空间关系判断函数,设计具体查询系统实践举例证明。     

对于线状地理特征空间关系的自然语言理解

人们通常用定性的词汇描述空间关系,而地理信息系统都采用定量的方法,这就限制了地理信息系统表达地理空间信息的能力。为了建立自然语言表达的空间关系和空间关系计算模型之间的桥梁,开发能更容易被广大的非专业人士使用掌握的自然语言的地理信息系统界面,充分理解自然语言所表达的空间关系和物体是十分必要的。本文通过认知实验的方法研究了英语自然语言对两个线状地物的空间关系的理解,发现地理特征之间的几何关系和拓扑关系是影响人们对空间关系的描述的主要影响因子,并且在不同的情况下,它们的影响程度不同。研究还发现,在有些情况下上下文的语境也对空间关系的描述有一定的影响。     

扩展SPARQL的室内空间语义查询研究

针对室内空间特点以及人类对室内位置服务的迫切需求,探讨了适合室内空间语义查询的方法。基于全息位置地图室内空间本体模型,描述室内空间对象及与之相关的人、事的属性信息及其关系,以室内空间本体概念及其属性作为查询原语,增加查询函数实现室内特有的空间关系（如“对面”、“楼上”和“楼下”等）的计算与查询,扩展了SPARQL查询语言基本语法。设计了室内本体查询语言IndoorSPARQL,开发自定义查询语言解析器,初步实现了顾及空间计算的室内空间语义查询。最后,利用Protégé本体建模工具对试验区进行本体实例建模,采用自定义查询语言IndoorSPARQL进行室内语义查询,并将结果可视化。实验结果表明,基于自定义语言IndoorSPARQL的查询方法可有效地支持顾及室内空间计算的复杂语义查询。     

网络地图服务中空间查询与分析的栅格化实现

地理信息获得了越来越广泛与深入的应用.空间查询与空间分析是GIS(Geography Information System,地理信息系统)的核心特征之一,也是空间信息服务(如Web Feature Service)实现中的关键问题.如何在网络地图服务场景下提供高效能的空间查询与空间分析功能是网络地图服务器设计与实现中的...     

可扩展的分布式矢量空间数据库集群原型系统研究

空间数据获取手段呈现多样化,其数据集每天以PB级的速度在增长,如何高性能地存储、高效处理海量空间数据成为重点问题。基于空间数据库集群系统,提出了Geohash的矢量空间数据分片存储方法,通过该分片方法实现了空间数据的并行导入、分布式矢量空间数据查询。通过实验分析了分布式矢量空间数据库在真实数据集以及虚拟数据集下的读写性能。实验表明:考虑空间分布特征的分布式空间数据库集群在空间查询性能和并发访问性能方面具有更好的扩展性。     

一种异构多核架构快速查询多边形图层间空间关系的方法

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。