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

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

空间连接优化方法的研究

基于MBR及直接查询谓词，提出了能够优化多路R树连接筛选阶段的加权处理方法，扩展了R树结构及MRJ算法。使用该方法能够得到更加有效的候选集，减少磁盘访问次数，节省了CPU及I/O的时间开销，通过实例验证了其在空间数据库查询优化方面的优势。     

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

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

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

单机运行环境难以满足海量空间数据的连接聚集操作对时空开销的需求,集群上的并行计算是高效处理海量空间数据的连接聚集操作的关键. 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树的非增量递归算法。该算法采用深度优先递归搜索策略,同步遍历n个空间数据集对应的R树,算法结束时,同时返回K个距离最短的n元组。并且采用基于距离的平面扫描技术对该算法进行了优化,有效减少磁盘访问次数和CPU响应时间。最后,通过实验验证了算法的有效性。     

基于主存R树的空间连接的实现

空间查询效率是衡量数据库性能的关键，而空间连接查询是最耗时、最重要的空间查询。对几种典型的空间连接方法作了简单回顾，并具体给出了基于R树的空间连接算法(RJ)在空间数据库管理系统SADBS中的实现。     

面向GML的渐进式合并空间连接查询

在面向地理数据服务的空间数据集成系统中,常常需要对由地理数据服务动态生成的GML做进一步的空间连接查询处理才能得到用户最终的查询结果.研究并提出了一种面向GML的渐进式合并空间连接查询处理算法PrMSJ,其主要思想是改造传统基于划分的空间合并连接算法,使之能够以渐进的方式处理面向GML的空间连接查询;提出了一种基于驻留度的动态同步替换策略(DCFP)处理内存溢出;还提出了一种基于完备参考点的方法进行冗余结果检测.实验结果表明,所提出算法优于现有的渐进式空间连接查询处理算法.     

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

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

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

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

一种优化的空间连接算法

空间数据库中空间连接操作是最重要、最耗时的操作之一,基于BFRJ算法研究了一种对中间连接索引优化排序的空间连接算法OBFRJ,该算法使用广度优先顺序对两棵R树进行同步遍历,对生成的中间连接索引采用了一种空间填充曲线进行排序,使得在下一层的连接时出现页错误的次数减少。实验结果表明,该算法在磁盘访问次数以及CPU代价上都要小于DFRJ和BFRJ算法。     

Reducing outer joins

We present a method for transforming some outer joins to inner joins and describe a generalized semijoin reduction technique. The first part of the paper shows how to transform a given outer join query whose join graph is a tree to an equivalent inner join query. The method uses derived relations and join predicates. Derived relations contain columns corresponding to join conditions and may have virtual row identifiers, rows and attribute values. The constructed inner join query, after elimination of virtual row identifiers, has the same join tuples as the outer join query. Both the theoretical maximum number of virtual rows and the average number in practice are shown to be low. The method confines consideration of the non-associativity of outer joins to a single step. The second part of the paper generalizes to outer joins the well known technique of semijoin reduction of inner joins. It does so by defining the notions of influencing and needing, and using them to define full reduction and reduction plans. The technique is applied here to perform one step of the method presented in the first part. Semijoin reduction is useful in practice for executing join queries in distributed databases.     

Alternative strategies for Performing Spatial Joins on Web Sources

With the current information explosion on the Web, numerous applications require access to a collection of different but related pieces of distributed geospatial data. In this paper, we focus on one set of such applications that requires efficient support of spatial operations (specifically, spatial join) on distributed non-database sources. The main challenge with this environment is that remote sources are usually read-only and/or do not support spatial queries. Moreover, several of these Web-based applications can tolerate either some level of inaccuracy or progressively filtered (or polished) results. Therefore, conventional distributed spatial join strategies are not applicable or efficient in this environment. To address these challenges, we first break down the process of distributed spatial join operation into three steps: (1) local to remote transfer, (2) remote spatial selection, and (3) local refinement. Then, for each step, we propose and study alternative techniques and by varying their combinations, we generate several query plans. Each plan strives to strike a compromise between efficiency and accuracy. Since the techniques proposed for the first step have significant impact on the overall performance of the query, we specially focus our attention on this step. We propose two heuristics for the first step to reduce either the number of selection queries or the area covered by each selection query. Within a realistic experimental set-up, we show that one heuristic is more appropriate with fast networks and a powerful local server, while the other one is superior in the opposite situation. Our experiments also show that both heuristics outperform approaches based on transmitting either the actual spatial objects or their bounding boxes. Note that the intention of this paper is not to propose a query optimizer to choose one plan over the others. Instead, it serves as a first step towards the design of such an optimizer by concentrating on the design and evaluation of several alternative plans within a realistic experimental set-up.     

海量3D点云数据压缩与空间索引技术

针对3D模型中海量点云数据压缩与空间索引低效问题和漫游过程中相邻两次查询窗口重叠是大概率事件问题,提出邻点差值渐进压缩和基于裁剪重叠区域进行冗余处理的R树空间索引方法。首先,利用八叉树对3D模型进行空间剖分,借助Morton码对每个叶节点管理的点云数据排序,按照R树叶节点的外接立方体大小对数据进行分块,计算块内相邻点数据差值,以块为单位渐进压缩差值,批量读取这些数据块创建R树;其次,借助上次查询窗口范围计算本次查询有效范围;最后,给出基于R树索引的点云数据查询方法。该方法使点云数据压缩率提高了26.61个百分点,并能实现流式传输,同时减少了I/O开销,使其查询性能提高了35.44%,数据冗余减少了16.49个百分点。实验结果表明,所提方法在3D虚拟旅游、数字城市等系统具中有明显优势。     

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

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

一种新的基于划分的结构连接算法

有效的结构连接是XML查询处理的关键。目前，大部分结构连接算法由于需要临时排序、建立索引或存在数据复制及I/O问题，大大降低了执行效率。该文在分析比较现有结构连接算法的基础上，提出了一种新的基于划分的结构连接算法。该算法不需要排序或建立索引，通过栈的机制解决了数据复制问题，并充分考虑内存缓冲提高了I/O性能。实验分析表明该算法具有良好的查询性能。     

面向数据联邦的安全多方θ-连接算法

近年来,多个国家地区出台了一系列数据安全相关的法律,例如欧盟的《通用数据保护条例》等.这些相关法律法规的出台,加剧了各企业机构等多方之间数据共享难的数据孤岛问题.数据联邦(data federation)正是解决该问题的可能出路.数据联邦是指多个数据拥有方在不泄露各自原始数据的前提下,结合安全多方计算等隐私计算技术,联合完成查询任务的计算.这一概念已成为近年来的研究热点,并涌现出一系列相关的代表性系统工作,如SMCQL、Conclave.然而,针对关系数据库系统中核心的连接查询,现有数据联邦系统还存在如下问题:首先,连接种类单一,难以满足复杂连接条件下的查询需求;其次,算法性能低下,由于现有系统往往直接调用安全工具库,其运行时间与通信开销高昂.因此,针对以上问题进行研究,提出了数据联邦下连接算法.主要贡献如下:首先,设计实现了面向多方的联邦安全算子,能够支持多种运算;其次,提出了支持θ-连接的联邦连接算法与优化策略,显著减少了连接查询所需安全计算代价;最后,基于基准数据集TPC-H,验证了该算法的性能.实验结果表明,与现有数据联邦系统SMCQL、Conclave相比,该算法能够将运行时...