受限空间连接查询及代价分析

针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题,提出了受限的空间连接查询,在给定查询范围内找到满足某种空间谓词的空间对象,给出直接解决方法和基于R-树的受限空间连接查询算法.基于QR树的优良特性,提出一种基于QR树的受限空间连接查询算法,该算法既避免了四叉树的较大存储代价,又克服了R树的节点重复的弊端,使得受限空间连接查询可以在多棵较小的R树上进行,较好地解决了空间连接查询开销较大的问题.对所提出的算法进行代价分析,实验证明算法具有较高效率.

基于R-树索引的Map-Reduce空间连接聚集操作

空间连接聚集是一种常用并且非常耗时的空间数据库操作,特别是在面对大规模空间数据集时,单机运行环境难以满足其对时空开销的需求,如何设计高效的面向云计算环境中的分布式空间连接聚集算法越来越受到人们关注。Map-Reduce作为云计算的核心模式受限于其扁平化的串行扫描操作模型,常被用来加速非索引的空间连接操作,现有工作尚无将Map-Reduce和R-树索引结合来处理空间连接聚集。因此,提出了基于R-树索引的Map-Reduce空间连接聚集算法(RSJA-MR)来更高效地返回连接聚集结果。提出一种分布式R-树索引结构以支持大规模空间数据的索引,RSJA-MR算法利用分布式R-树生成任务集,任务集的执行满足无依赖并行计算模式,很容易在Map-Reduce框架中进行表达。文中提出一种实时缓存策略以支持索引并发访问。实验结果表明:相比非索引的Map-Reduce连接聚集算法,在空间交叠连接聚集查询上,时间性能最少提升8%,在空间包含连接聚集查询上,时间性能最少提升近35%。

基于直角多边形近似的空间连接查询

空间查询效率是衡量空间数据库性能的关键 ,而空间连接查询是最耗时、最重要的空间查询 .本文在分析了空间连接以往工作的基础上 ,采用一种新的空间近似方法——直角多边形近似 ,改进空间对象的近似精度 ,并用于基于 R树的空间连接方法 ,给出了连接算法 ,并用实验验证了方法的有效性 .

一种有效的空间连接算法

介绍了一种改进的基于striped-sweep算法的SPBSM算法,并和基于list算法的PBSM算法和基于trie的TPBSM算法进行比较。这种改进的SPBSM算法克服了其它两种算法的不足,有效地提高了空间连接算法的性能。

派生索引空间连接查询

空间连接查询是最耗时、最重要的空间查询 .针对空间多路连接中一方有 R树索引 ,另一方是连接或选择的中间结果 ,因而无索引的情况 ,提出派生索引连接方法 .这一方法基于父母索引为中间结果建立派生索引 ,以用于随后的空间连接 .分析其查询花费 ,用于多路连接的查询优化 .最后用实验结果说明方法的有效性 .

并行空间连接查询处理

基于顺序空间连接查询的效率不能令人满意 ,利用并行机制提高空间连接查询效率 .空间连接查询的并行处理方法最重要的特征是任务分配根据多路平面扫描顺序 ,避免了连接处理过程中处理器之间的通信花费 .提出基于空间连接花费模型的任务分配方法和基于花费估计的动态任务分配策略 ,并给出了花费模型 .

空间信息网格中远程空间连接查询的优化

随着空间信息网格的建设,网格平台上管理的空间信息资源越来越丰富,这促进了空间信息网格中空间数据分布式查询的应用需求,而在分布式空间查询中,空间连接查询操作往往成为性能的瓶颈。根据空间信息的特点,通过利用网格计算资源来优化空间连接查询的执行。首先基于网格服务构建网格平台分布式空间数据查询软件结构,通过设计远程空间连接执行服务利用网格平台中的计算资源;根据空间信息的特点,采用基于Kd-Tree空间分区并行连接的方法提高远程空间数据连接操作执行效率,并给出了远程空间连接执行的查询代价模型;然后根据连接代价模型设计了远程空间连接查询执行计划优化生成算法;最后总结了本文工作并探讨了下一步研究方向。

空间连接处理中提炼步骤的遗传优化

内务处理是用来优化空间连接处理提炼步骤的I/O代价,属于NP-难的问题,现有求解方法复杂度太高.本文将页面聚簇和聚簇调度问题分别归约为图的k划分和最长路径问题,提出了改进的遗传算法和基于最大生成树的近似算法进行求解.对经典遗传算法的进行了修正以满足页面聚簇划分约束.近似算法的解大于最优解的一半.理论分析和仿真实验验证了算法的可行性和有效性.

一种优化的空间连接算法

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

基于R-Tree的空间连接代价模型的改进

对基于R-Tree的空间连接代价模型进行了探讨,主要研究了HUANG Y W提出的空间连接代价模型。利用最优/最差选择策略降低该算法的时间复杂度,对基于缓冲区的代价模型提出了改进后的评估公式,通过实验验证了改进后的模型比原模型提高了评估的精确度。

改进的基于R树的空间连接代价模型

针对Yannis Theodoridis等人提出的空间连接代价模型存在比较理想化的限制条件——假设数据均匀分布,缓冲策略使用简单的缺点,利用划分子空间并抽样获取非均匀数据实际密度的策略,提出了优先保存查询集合树的最新访问路径的有效中间节点的缓冲区算法,给出了改进后的评估公式。实验结果表明,改进后的模型比原模型提高了评估的精确度。

轨道交通节点与商业建筑的空间连接模式

通过研究国内外轨道交通和商业建筑的空间关系,归纳出轨道交通节点与商业建筑的三种空间连接模式,并以长沙市五一广场为例,提出了相关的连接策略和空间构想。

多路空间连接优化算法研究

在深入分析各种空间连接算法特点的基础上,提出一种可以有效提高多路空间连接效率的优化方法.该方法一方面针对空间数据的聚类特性,提出了获得更加紧凑的R树索引结构的算法;另一方面考虑连接顺序对多路空间连接算法性能的影响,提出基于R树连接的多路空间限制策略和多路平面扫描技术,从而优化数据集参与连接的顺序选择,并在此基础上给出优化的多路连接算法.通过实验验证,本文的优化方法能够有效的提高多路空间连接查询效率,尤其是在耗时较大的链图查询上.

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

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

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

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

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

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

面向并行空间连接的两轮映射数据划分方法

针对数据划分结果高冗余、低均衡可能会增加系统的工作负荷和影响系统的负载均衡这一问题,提出两轮映射数据划分方法.在第一轮映射中,通过充分利用划分对象的空间属性来减少冗余数据,通过合理设置阈值来均衡划分数据;在第二轮映射中,通过动态映射机制,提高划分结果的数据量均衡度.与Oracle Spatial数据划分方法、线性编码轮询调度划分方法以及Hilbert编码轮询调度划分方法进行比较可知,采用两轮映射方法可以有效地控制冗余数据的产生,大幅提高划分结果的数据量均衡度,具备较好的划分效率.

对象管理的空间连接策略与算法

空间连接是空间数据库对象管理研究的一个至关重要问题，也是近年来研究的热点之一．本文讨论了对象管理的空间连接策略与过滤机制，并在G树的基础上提出一种新的空间连接算法，有效地解决了空间对象连接的效率问题．

模型误差变化率有界的空间连接系统鲁棒性能分析

针对具有时空不变名义模型的空间连接系统,讨论其存在有界、线性、时空变化和有结构性约束的模型误差时,取得鲁棒性能的条件.对于时间轴和空间轴,分别定义了算子的时间变化率和空间变化率,给出了系统取得鲁棒性能时该变化率的上界和下界.研究表明,对于时间轴和空间轴上变化率满足一定条件、具有结构约束的有界模型误差,系统取得鲁棒性能的充分必要条件是存在频率域上的缩放矩阵(D标度),使得系统名义模型范数小于1.

基于4CDRS的空间连接查询

提高空间查询效率是空间数据库方面备受关注的一个问题,而空间操作交运算又是最常用的谓词.空间操作交运算的主要对象是多边形和线,针对空间线对象,通过存储线的偏移方向,来保存线的走向的这样一种对象压缩的近似栅格表示,并且用不同颜色代表了对象和单元格之间不同的相交类型.这种新的栅格近似即四色偏移栅格标识图(4CDRS).将4CDRS用作查询处理中的过滤器,并设计出相应的测试算法.