一种多路空间距离连接查询处理方法

为了解决多路空间距离连接查询问题,提出了一种基于R树的非增量递归算法。该算法采用深度优先递归搜索策略,同步遍历n个空间数据集对应的R树,算法结束时,同时返回K个距离最短的n元组。并且采用基于距离的平面扫描技术对该算法进行了优化,有效减少磁盘访问次数和CPU响应时间。最后,通过实验验证了算法的有效性。     

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

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

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

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

空间连接优化方法的研究

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

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

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

空间数据库中连接运算的处理与优化

空间数据库的性能问题严重制约了它的应用与发展 .由于空间连接运算是空间数据库中最复杂、最耗时的基本操作 ,因此其处理效率在很大程度上决定了空间数据库的整体性能 .尽管目前已经有许多空间连接算法 ,但空间连接运算的代价估计和查询优化仍然有待进一步研究 .众所周知 ,大部分空间连接算法都是基于 R树索引实现的 ,如果参与空间连接运算的关系上没有索引或只有部分索引 ,那么就需要使用特殊的算法来处理 .另外 ,各种算法的代价评估模型需要一个相对统一的计算方法 ,实践证明 ,根据空间数据库的实际情况 ,使用 I/ O代价来估计算法的复杂性较为合理 .在此基础上 ,针对复杂的空间查询中可能出现多个关系参与空间连接运算的情况 ,故还需要合理地应用动态编程算法来找出代价最优的连接顺序 ,以便最终形成一个通用的算法框架 .通过对该算法框架的复杂性分析可以看出 ,在此基础上实现的空间数据库查询优化系统将具有较高的时空效率 ,并且能够处理非常复杂的空间查询     

一种有效的时空连接算法*

对空间数据库中静态数据集与动态数据集的连接问题进行了研究,提出了一种时空连接算法。该算法使用广度优先顺序对R-tree和TPR-tree进行同步遍历,在连接计算时,使用一种收紧MBR的剪枝策略对TPR-tree的节点进行剪枝,直到两棵树的叶子节点,最后计算R-tree每个叶子节点的最近邻。通过实验表明,算法有效解决了为静态数据集中的所有对象在动态数据集中查找到某个未来时间的最近邻的问题。     

一种基于R*树的自相似性连接算法

相似性连接是很多研究问题的基础,不少实际问题也都可以归结为相似性连接。针对两个输入集合相同的相似性连接问题,以R*树作为索引结构,提出一种高效的自相似性连接算法Self-SJ,返回最相似的k个对象对。该算法利用了分支界限思想,在使用剪枝策略减少候选对象对的同时,也避免了重复节点对的计算,因而比传统的基于R*树的算法更加快速。在真实数据集上的实验表明,Self-SJ不仅具有更短的运行时间,对于参数k也具有良好的可扩展性。     

一种全新的R树节点选择算法

在 R树插入算法中采用全新的节点选择算法 ,一改传统的从根节点开始自上而下的节点选择方案 ,而是从叶节点层开始 ,先自下而上再自上而下地选择叶节点 ,较好地解决了同层节点重叠所导致的查询效率低下的问题。实验证明 ,提出的 R树空间索引方法 ,不仅在查询效率上明显优于 R*树,而且 R树生成的时间开销也减少了 50%左右 ,综合性能超过了 R*树 ,便于扩展到三维甚至多维空间中 ,以实现对空间数据和时空数据的高效查询功能。     

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

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

A top-k spatial join querying processing algorithm based on spark

Aiming at the problem of top-k spatial join query processing in cloud computing systems, a Spark-based top-k spatial join (STKSJ) query processing algorithm is proposed. In this algorithm, the whole data space is divided into grid cells of the same size by a grid partitioning method, and each spatial object in one data set is projected into a grid cell. The Minimum Bounding Rectangle (MBR) of all spatial objects in each grid cell is computed. The spatial objects overlapping with these MBRs in another spatial data set are replicated to the corresponding grid cells, thereby filtering out spatial objects for which there are no join results, thus reducing the cost of subsequent spatial join processing. An improved plane sweeping algorithm is also proposed that speeds up the scanning mode and applies threshold filtering, thus greatly reducing the communication and computation costs of intermediate join results in subsequent top-k aggregation operations. Experimental results on synthetic and real data sets show that the proposed algorithm has clear advantages, and better performance than existing top-k spatial join query processing algorithms.     

Native XML数据库的结构连接算法研究

Native XML数据库的快速查询,可以通过基于XML文档编码的结构连接算法实现。在对现有结构连接算法进行综述的前提下,提出一种新的Native XML数据库的结构连接算法——基于深度均匀划分的结构连接算法(DRIAM)。该算法不要求输入数据AList和DList有序或在其节点编码上建有索引,避免了排序和索引所增加的额外开销;不需要输入数据AList和Dlist全部加载到内存中,可以适应不同内存大小限制的情况,并且该算法时间复杂度非常低。     

Optimal parallel scheduling of M-way join queries

The problem of computing multirelation (M-way) join queries on uniprocessor architectures has been considered by many researchers in the past. This paper lays the necessary foundation for work involving optimization of M-way joins in parallel architectures. We explain the inadequacies of previous uniprocessor strategies and describe a more suitable formulation based on the concept of matching in graph theory to approach the problem in a parallel environment. It has been shown that the problem of optimizing M-way joins is an NP-hard problem and hence we would expect that in a parallel processing environment the search space of possible solutions (join schedules) would be enormous, especially when a variable number of processors are considered. Our strategy seeks to reduce the region to search by partitioning the search space according to the number of available processors. Based on this a significant portion of the search space, which will produce non-optimal join schedules, may be ignored.     

一种有效的并行数据库动态负载平衡连接算法

在基于Shared-nothing结构的并行数据库中,负载平衡一直是影响查询处理性能的重要因素。在数据库中频繁使用的连接操作会因为各种因素导致的负载倾斜和额外的通讯开销而降低数据库的整体性能。提出了一种基于RCMD分布方法的动态负载平衡连接算法,能够在连接操作的执行过程中动态调整各个结点的负载。理论分析和实验结果证明提出的算法能够有效地平衡负载,提高并行数据库的执行效率。     

R*-树空间索引的优化研究

针对大型空间数据库应用的需求及己有空间索引技术的不足,在论述R-树及R*-树索引技术的相关概念、数据结构、算法描述及性能分析的基础上,提出了一种改进的R*-树空间索引结构。研究结果表明：改进后的R*-树与原始的R*-树相比具有更高的性能。