基于DPR树的分布式并行空间索引机制的研究

针对分布式并行环境下海量空间数据管理与并行化处理的效率问题,以提高分布式并行空间数据的查询效率为目的,根据现有的空间索引结构与并行化技术,提出一种新的分布式并行空间索引结构--DPR树.DPR树是空间索引技术与并行化技术优化结合的成果.DPR树在数据的总体划分与部分查询中所采用的均是基于高效处理技术.它在原有的并行Master-client R树的基础上进行改进,采用了HCSDP数据划分技术,并将其应用到分布式环境下,且每个节点机中各子树采用了改进的R树--R*Q树.通过性能分析表明,该索引结构具有高效的查询性能.     

集群上一种面向空间连接聚集的并行计算模型

单机运行环境难以满足海量空间数据的连接聚集操作对时空开销的需求,集群上的并行计算是高效处理海量空间数据的连接聚集操作的关键. Map-Reduce是云计算中一种应用于大规模集群进行大规模数据处理的分布式并行编程模型,分析发现,Map-Reduce并不直接支持以既高效又自然的方式来处理具有二次归约特征的并行空间连接聚集操作.因此,提出了一种并行计算模型——Map-Reduce-Combine（MRC）来有效地处理大规模空间数据的连接聚集操作.MRC在Map-Reduce 模型上增加一个Combine阶段,有效地合并分散在各个Reducer的部分聚集结果.针对并行任务划分中空间对象的单分配问题,提出了过滤优化算法,提高了MRC下处理空间连接聚集查询的效率.实验验证所提出的并行计算模型在处理空间连接聚集查询时具有良好的效率、有效性、可扩展性和简单性.     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

平面线段集最近邻查询算法

针对基于R-树的空间索引结构存在的节点覆盖冗余,兄弟节点之间的交叠问题,提出一种新的空间索引结构即RP-树。通过最适合划分函数和数据矩形的有序关系来对空间数据进行划分,使得该树的高度尽可能低,节点交叠较小。以RP-树为平面线段集的索引结构,利用线段集的相关定理和筛选规则,给出了一个求解平线段集最近邻的新查询算法,该算法不仅易于理解,且执行效率较高。     

基于Hadoop的分布式CIF四叉树索引方法

针对矩形空间数据对象,以传统CIF四叉树索引技术为基础,利用Hadoop平台与MapReduce并行编程模型,采用“分而治之”的思想,对数据空间进行划分,设计适用于分布式环境的创建索引、相交查询、区域删除的并行算法。在此基础上,通过改变数据集中矩形对象的数目与map数进行实验,分析并行创建与相交查询的效率。实验结果表明,对于大数据量的数据集与多数据集,并行创建与查询可以提高处理效率。      

RTC树的构建与不确定近邻关系查询方法

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.     

一种有效的空间数据仓库区域聚集查询索引结构

空间数据仓库有效地支持对空间数据的管理和分析，提供更加全面的决策支持．讨论了一种有效的空间决策支持手段——空间区域聚集查询的实现．基于aggregate cubetree和aR—tree提出了一个可以有效地在空间维和非空间维上进行区域聚集查询的索引结构aCR-tree及其相关算法，并计算分析了查询算法的时间复杂度．与现有技术相比aCR-tree降低了存储代价和每次查询访问的节点数，通过实验证明，该索引结构可以提供较好的存储性能和查询性能．     

开源关系数据库集群的并行空间连接算法实现

当前对并行空间连接查询的研究主要集中在算法设计上,缺少在并行关系数据库管理系统上的应用实现研究.通过分析并行空间连接算法流程,利用开源并行关系数据库集群项目PL/Proxy,提出了混合式计算迁移模式并扩展了对空间操作的支持,并在其上实现了可扩展的基于空间划分的并行空间连接算法.通过真实数据的实验表明：设计实现的并行空间连接算法在空间数据划分负载均衡的情况下,可实现近线性的加速比;而在空间划分产生数据倾斜严重的情况下,仍具有一定的加速比,同时具备针对空间划分方案改进的可扩展能力.算法的实现方式为进行并行空间数据管理研究提供了一种可行的解决方案.     

Hilbert填充曲线与空间分布模式探测的点数据集空间划分方法

空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。针对点数据集多目标空间划分问题,引入Hilbert空间填充曲线和空间分布模式探测过程,提出针对规则、随机和聚集分布模式的点数据集空间划分方法。实验结果表明,该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度3种约束条件。     

IRT树索引结构的研究

论文针对R树在处理一些特定空间数据对象集时的不足,研究了基于最小外接直角等腰三角形(MIRT)的新的索引结构—IRT树。探讨了IRT树的空间平面划分和空间数据结构特征,给出了IRT树的节点分裂算法和搜索算法。进一步对IRT树和R树进行了比较分析。由分析可知,对于一些特定数据集,IRT树在查询准确率、数据存储和空白空间冗余方面均有一定的优势。     

基于多路归并的空间矢量数据库构建方法

在构建空间矢量全球四叉树数据库时,四叉树矢量结点的生成可能涉及海量矢量数据的读取。针对上述情况,提出基于多路归并的建库方法,以外排序的方法解决内存限制问题,采用矢量层分割自然形成的结点顺串以及内存文件映射技术存取结点顺串,使矢量建库的效率得到保证。实验结果证明该建库方法效率高。     

分布式入侵检测中基于能力与负载的数据分割算法

针对高速网络环境下分布式入侵检测中海量数据并行检测处理的效率和检测率问题,提出一种基于能力与负载的数据分割算法。该算法依据采集到的集群内各数据分析节点的系统性能指标及运行状态,评估节点的数据处理能力与负载程度。基于节点的能力与负载适应因子,权衡节点在集群中检测和分析数据能力的权重,实现海量数据在集群内各数据分析节点间的动态数据分割,为节点分配适应其能力与实时负载的数据粒度。仿真测试结果表明,该算法具有较好的负载均衡性,降低了系统的检测时间,提高了数据并行处理的效率和检测率。     

A Taxonomy of Spatial Data Integrity Constraints

Spatial data quality has become an issue of increasing concern to researchers and practitioners in the field of Spatial Information Systems (SIS). Clearly the results of any spatial analysis are only as good as the data on which it is based. There are a number of significant areas for data quality research in SIS. These include topological consistency; consistency between spatial and attribute data; and consistency between spatial objects representation and their true representation on the ground. The last category may be subdivided into spatial accuracy and attribute accuracy. One approach to improving data quality is the imposition of constraints upon data entered into the database. This paper presents a taxonomy of integrity constraints as they apply to spatial database systems. Taking a cross disciplinary approach it aims to clarify some of the terms used in the database and SIS fields for data integrity management. An overview of spatial data quality concerns is given and each type of constraint is assessed regarding its approach to addressing these concerns. Some indication of an implementation method is also given for each.     

基于空间分割的数据简化和分类

数据简化的目的是简化数据集并保留有用的分类结构 .本文提出一个基于空间分隔的数据简化和分类算法 ,该算法将常规数据库的记录映射到多维空间上 ,从而将数据简化过程转变成在多维空间中同类数据的空间合并问题 ,也就是多维空间中不同类数据的空间分隔问题 ,最终得到一系列分隔空间 ,达到数据简化和分类的作用 .该方法用现实世界的 7个数据集进行评估 ,并与 C4.5所获得的结果进行比较 ,效果是显著的 ,并且结果唯一     

基于节点负载的数据动态分区

一种基于节点负载的数据动态分区系统,主要考虑节点CPU、内存、带宽负载情况,首先采用二次平滑法预测节点的负载,再结合AHP和熵值指标权重法得到每个节点的处理能力,最后针对不同应用场景动态地调整系统的负载均衡性,提高应用的响应速度;该系统主要包括负载监测采集、预测、数据预分区、数据迁移等模块.由于分布式环境存在节点资源的异构性,为了数据分析计算过程中减少节点之间数据的传输,充分利用节点计算资源,通过负载均衡性提高应用分析的并行计算速度.为此,本文提出一种基于节点负载的数据动态分区机制和策略来改善系统负载均衡性及提高应用的响应速度,辅助相关工作人员完成决策.本论文结合Spark和Elasticsearch集成的数据分析应用场景进行测试.     

GIS权籍空间数据的存储与查询

探讨了基于关系型数据库存储XML权籍对象的方法和技术。分析了数据库存储XML数据的类型,论述了运用XML存储和管理权籍对象的可行性。基于GML规范建立了权籍对象的概念模型和逻辑模型,并根据XML权籍对象之间的关系,给出了将权籍对象转换到关系型数据库的方法,基于此实现了权籍对象空间关系的查询与应用。     

基于RDBMS的空间数据管理模型及在土地产权产籍系统中的实现

利用关系型数据库来管理空间数据是当前ＧＩＳ研究的热点和前沿领域之一,该文提出了一种空间数据库引擎数据结构模型,分析了数据模型体系结构、数据组织以及空间图形要素表达,进而根据该结构模型,实现了在ＳＱＬ Ｓｅｒｖｅｒ关系型数据库中对空间图形数据进行存储、拓扑运算和拓扑分析的操作,通过在土地产权产籍系统中的实际应用表明,基于该模型开发的空间数据库引擎Ｓｐａｔｉａｌ Ｄａｔａｂａｓｅ Ｇｕｉｄｅ（ＳＤＧ）     

基于ArcSDE与OracleSpatial集成技术的空间数据设计方法

针对当前空间数据库随着数据量增大和数据种类增多运行效率降低的问题,该文通过分析当前的空间数据库和空间数据引擎技术,提出一种基于ArcSDE和Oracle Spatial集成技术的空间数据库设计方法。通过对空间数据库里的不同格式的数据进行合理组织,从而实现提高空间数据库的性能和效率的目的。     

基于密度的并行聚类算法

为满足大规模空间数据库的聚类需求,面向计算机集群,提出一种基于密度的并行聚类算法。该算法根据数据库分布特征进行数据分区,在每一个节点上对数据块并行聚类,在主节点上合并聚类结果。实验结果表明,该算法的计算速度随着节点数的增多呈线性增加,具有较好的延展性。     

城市应急联动系统架构与统一模型研究

根据我国对城市应急联动系统(UERS)建设的要求,遵循软件工程领域内成熟的模型语言规范,设计一个基于统一建模语言的UERS模型,包括决策指挥中心、应急联动中心、各联动单位的调度中心、联动单位的分支机构、处置力量部门和处置力量编组。该模型可以协助系统开发人员规范系统的开发与软件重用,优化系统结构,加快UERS的开发进度。