一种改进的并行连接算法Diag-Join及其性能分析

介绍了一种改进的并行连接算法:Diag-Join算法,并将它运用到并行环境中。实验表明,Diag-Join算法在内存足够时可以取得最好的性能,即使在内存较小的情况下,仍能得到令人满意的效果。

两类联图的PI不变边

设G=(V(G),E(G))是一个简单连通图。图G的PI指标定义为PI(G)=∑_(e=uv∈E(G))[n_(1)^((e|G))+n_(2)^((e|G))],其中n_(1)^((e|G))是图G中到点u的距离比到点v的距离小的点的数目,n_(2)^((e|G))是图G中到点v的距离比到点u的距离小的点的数目。如果PI(G-e)=PI(G),那么边e称为图G的PI不变边。本文中分别讨论门槛图和轮图存在PI不变边的条件。

大规模时空轨迹数据连接查询效率优化实践

本文提出一种低集群计算资源条件下,大规模轨迹类数据同时空关系的快速连接查询算法DPCP-CROSSJOIN.该算法通过对轨迹数据时间字段进行分段交叉编码和位置网格化等方式对连续的轨迹数据离散化,并以日期和网格区域编码进行两级分区存储.通过交叉“等值”连接查询,实现时空连接查询的三级索引、四级加速,将n·n对象间同时空关系连接查询时间复杂度从O(n^(2))降为O(nlogn).在Hadoop集群上使用Hive和TEZ等进行大规模轨迹数据连接查询时能将连接查询效率最高提升到30.66倍.该算法以时间段编码作为关联条件,巧妙绕开连接过程中复杂表达式的实时计算,以“等值”替代复杂表达式计算连接,提高MapReduce任务并行度,提升集群存储和计算资源利用率.在面对仅使用一般优化已几乎无法完成的,更大规模类似任务,仍能在数分钟内完成.实验表明,该算法具有高效和稳定等特性,尤其适用低“算力”资源条件下大规模轨迹数据的同时空关系连接查询.此方法还可作为时空轨迹伴随查找,对象间关系亲密度判定等的原子算法,可广泛应用于维护国家安全、社会治安秩序,预防和打击犯罪,辅助城乡规划统筹等领域.

pgi-distance:一种高效的并行KNN-join处理方法

KNN-join是一种新近才提出的操作,它在数据挖掘中有着广泛的应用.利用KNN-join的"一次一个集合"的性质,一些数据挖掘任务,例如分类、例外挖掘和聚类等,就会更加容易地进行.MuX和Goreder则是两种专为KNN-join设计的算法.为了综合利用这两种方法的优点,一种新的KNN-join并行处理方法——pgi-distance(parallel grid index-distance)——被提了出来.pgi-distance使用双层结构,可以对I/O和CPU进行同时优化;基于距离的索引能够让它更好地适应数据维度和分布的变化.由于采用的是各DBMS厂商广泛支持的B+树索引,这让pgi-distance得以成为一种更为实用的KNN-join处理方法.在合成数据集和真实数据集上的测试也表明pgi-distance是实用的和高效的.

Join-based算法在Matlab中的实现

Join-based算法是一种著名的空间co-location模式挖掘算法,co-location模式代表的是一组空间特征的子集,它们的实例在空间中频繁的关联。首先描述了Join-based算法的工作原理,然后以挖掘三江并流珍希植物的共生物种问题为例利用matlab进行了程序实现,给出了运行的最优结果。

基于图结构索引的分布式OLAP加速方法

随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式OLAP打破单机存储的限制,可以将数据放在内存中以提升OLAP的处理性能.然而,基于内存的分布式OLAP在消除磁盘I/O后,性能瓶颈转移到了连接操作.连接操作是OLAP中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存OLAP系统MonetDB从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这3个重要方面,进行一系列设计与优化,以提升系统的分布式OLAP处理性能.测试结果表明,在TPC-H标准测试中,基于图结构索引的连接操作对于有连接操作的查询的平均性能提升达1.64倍(最多达4.1倍).对于这些查询中的连接操作,性能提升达9.8–22.1倍.

数据仓库中的一种提高多表连接效率的有效方法

联机分析处理OLAP查询经常涉及多表连接,所以提高多表连接的性能就成了提高OLAP查询处理的关键性问题·针对目前直接提高多表连接效率的方法、并行多表连接算法和连接索引,提出了变形多表连接索引·该方法基于使用SQL语句表述的查询模型库QMB建立一系列符合条件的变形多表连接事实表,并建立这些变形多表连接事实表的索引·在特定的多表连接查询中,变形多表连接事实表能替代原事实表与各维表连接,并在查询处理过程中动态更新·理论分析和实验结果表明,该方法可以有效地提高多表连接的查询效率·

MapReduce优化技术综述

作为一种处理大数据的并行编程模型,MapReduce由于其良好的可扩展性、可用性、容错性,得到了学术界和工业界的关注。针对MapReduce在应用领域中的不足,已经存在大量的优化技术。介绍了MapReduce框架,比较了现存的MapReduce列存储、索引、连接、迭代计算、科学计算及调度算法方面的优化技术,分析了MapReduce技术研究的挑战性问题,指出了未来研究方向。

一种基于向量索引的内存OLAP星型连接加速新技术

星型连接是OLAP中重要的操作,事实表与维表基于星型连接执行多维分析处理.星型连接的性能取决于连接性能.当前研究主要集中在如何在不同的处理器平台上优化哈希连接性能,然而如何获得最优的哈希连接参数或实现是一个复杂的问题.哈希连接不依赖于模式的语义信息,然而却可以在事实表与维表之间通过维映射特征进一步优化连接性能.该文提出了一种新颖的面向OLAP负载的向量索引以提高事实表与维表之间的连接性能.从模式的角度来看,维表可以映射为向量索引,每一个事实表记录可以直接映射到向量索引上的相应位置,无须执行基于值匹配的哈希连接操作.从实现技术的角度看,向量索引是一种位图索引、字典表压缩、主外键参照完整性约束和连接索引相结合的技术.系统化的设计使向量索引可以扮演多种角色:(1)向量索引与位图索引类似起到过滤作用;(2)向量索引相对于只存储0或1的位图索引使用更多的位来表示更多的信息;(3)映射或创建自动增长的主键作为向量索引地址并且更新相应的外键,将主外键参照完整性约束转换为向量参照约束;(4)外键连接操作简化为通过外键值引用向量单元.基于向量索引,OLAP中代价大的星形连接可以抽象为向量索引计算,OLAP查询可以简化为基于向量索引的单表扫描处理.向量索引简化的设计不仅可以提升性能,而且降低了在GPU平台实现的复杂度.本文首先讨论了向量索引机制和如何在数据库中应用向量索引;然后设计向量索引更新机制,以保证在更新时向量参照约束;最后提出基于向量索引的OLAP框架来提高内存数据库OLAP性能.基于向量索引的星型连接可以用作GPU上的OLAP加速器,使CPU可以将计算密集型负载转移到高性能GPU平台来加速OLAP处理.实验结果表明向量索引更新代价较低,而向量引用性能收益较大.更重要的是,向量索引支持OLAP中的星形连接操作在内存数据库引擎之外进行加速,降低了内存数据库的CPU负载,或者将星形连接负载通过硬件级加速器,如GPU进行加速.基于向量索引的星型连接可以显著提升CPU和GPU平台上的星型连接性能,相对于内存数据库Vector,在SSB Q4.1查询可以获得最大3倍的性能提升,平均性能提升了1.2倍.

并发内存OLAP查询优化技术研究

基于多核处理器硬件技术和高并发查询负载需求,近年来的研究不仅关注于一次一查询模式的查询优化技术,而且也关注于一次一组模式的查询优化技术.通过将并发查询转换为共享负载,一些低访问延迟的操作,如磁盘I?O、cache访问,可以被多个并发的查询所共享.当前的研究通常基于共享查询操作符,如扫描、连接、谓词处理等,通过生成全局执行计划优化并发查询.对于复杂的分析型负载,如何创建优化的执行计划是一个具有挑战性的问题.在广泛使用的星形模型的基础上提出一种模板OLAP查询执行计划来简化查询执行计划,以达到最大化查询操作符利用率的目标.1)提出了基于代理键的连接索引技术,将传统的基于值探测的连接操作转化为内存数组索引引用(AIR),使连接操作的CPU效率更高并且支持聚集计算的后物化;2)并发查询的谓词处理简化为cache line敏感的谓词向量,在单次cache line访问中最大化并发查询谓词计算性能;3)通过多核并行实现技术在SSB基准上进行测试.实验结果表明:共享扫描和共享谓词处理能够将并发OLAP查询处理性能提升1倍.

海量数据上的近似连接聚集操作

连接聚集操作是一种常用并且非常耗时的数据库操作.相对于准确查询,满足用户给定置信区间的近似结果由于其快得多的响应时间,更受用户的欢迎.作者分析发现现有的工作无法以既高效又满足给定的任意置信区间方式来处理近似连接聚集,因此提出了一种新的算法——(p,ε)-近似连接聚集查询(pε-AJA)来有效地返回满足任意置信区间的近似连接聚集结果.文章提出且预计算两个数据结构:连接随机样本(JRS)和连接位置索引对表(JPIPT).利用JRS,pε-AJA向用户返回近似结果的快速响应.如果利用JRS得到的近似结果没有满足给定的置信区间,pε-AJA利用JPIPT获得更多的随机连接元组.文中提出一种采样算法来获得JPIPT给定数量的样本,并且利用获得的JPIPT样本,该文提出的算法可通过对连接表的一遍顺序扫描获得连接元组.该文还提供了JPIPT和JRS有效的构建和维护算法.实验结果表明:pε-AJA可以获得相对于准确查询1～5个数量级的加速,并且可以有效地完成JPIPT和JRS的构建和维护操作.

一种复杂多维层次的连接和聚集算法

由于数据仓库中存储着不同粒度、容量巨大的数据记录 ,所以如何有效地执行联机分析处理 (OLAP)查询操作 ,特别是连接和聚集操作 ,便成为数据仓库领域的核心问题之一 为此 ,提出了一种降低连接和聚集操作的新算法 (joinandaggregationbasedonthecomplexmulti dimensionalhierarchies,JACMDH) 算法充分考虑了复杂多维层次的特点 ,在原有的位图连接索引 (bitmapjoinindex)的基础上 ,采用层次联合代理 (hierarchycombinedsurrogate)和预先分组排序的方法 ,使得复杂的多维层次上的连接和聚集操作转化成事实表上的区域查询 ,从而在处理多维层次聚集的同时 ,提高了连接和聚集的效率 算法性能分析和实验数据表明 ,JACMDH算法和目前流行的算法相比 。

关于评价指标集并合理论和方法的研究

在评价中,评价目标相同,不同的评价者会提出不同的评价指标集。本文提出了一套解决评价指标集并合的理论及方法,主要包括任何两个评价指标集相关性的度量方法,不同评价指标集的并合规则,及并合后评价指标集权向量的确定方法等。

RM树:一种支持字符串相似性操作的索引

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树索引,消除了现有内存方法的缺点,并通过字符串聚类的方法提高了相似性操作的效率.该文通过大量实验结果证明了RM树的有效性.

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

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

模糊对象的空间Co-location模式挖掘研究

空间co-location模式表示的是空间对象的实例在一个相同的区域内频繁地空间并置.过去人们已经对确定及不确定数据的co-location模式挖掘问题进行了一些研究,但是针对模糊对象上进行的研究还没有.模糊对象在许多领域里都有着非常重要的应用,比如生物医学图像数据库和GIS.该文研究模糊对象的空间co-location模式挖掘问题.首先,定义模糊对象上空间co-location模式挖掘的相关概念,包括模糊参与率、模糊参与度等.其次,提出FB算法挖掘模糊对象的co-location模式.接着,提出了3种改进算法,包括剪枝对象、减少实例间连接、改进剪枝步,以提高挖掘性能、加快co-location规则的产生.最后通过大量的实验说明FB算法及其改进算法的效果和效率.

一种基于网格索引的空间连接查询处理优化算法

针对云环境下的空间数据连接查询处理问题,提出一种基于MapReduce框架的高效空间连接查询处理优化算法.该算法采用网格划分方法将数据空间划分成大小相同的网格单元,并将其中一类数据集中的每个空间对象,按照其中心点的位置划分到所在的网格单元中,从而避免了连接对象的复制,网格单元之间根据其所包含数据对象的交叠关系构建网格索引;对另一类数据集中的对象,仅将其复制到与网格单元中数据有交叠的网格单元,从而过滤掉不可能有连接结果的数据对象,大大减少了后续的连接计算代价.合成数据和真实数据集上的大量实验表明,本文提出的空间数据连接查询处理优化算法在性能上明显优于原有SJMR查询处理算法.

XML数据库结构连接算法之分析

结构连接是XML查询处理的核心操作,受到了计算机研究界的高度关注。高效的算法是高效查询处理的关键,目前已经提出许多结构连接的算法。本文介绍了几种典型的算法,并分析了这几种算法的优缺点。

应用聚簇索引的多连接查询优化方法

多连接查询优化是提高数据库性能的关键问题之一.查询优化主要针对连接等一些具有较高执行代价的操作进行研究.在分布式查询优化中,应同时考虑本地处理代价和传输代价.提出了一种应用聚簇索引来优化多连接查询的方法,旨在减小查询的代价.分析对比证明该方法具有较好的效果.

基于位图连接索引的复杂多维层次的连接和聚集算法

在ROLAP中往往涉及到大量数据的复杂即席查询，从SQL角度看，这些查询通常都包含多表连接和分组聚集操作。本文提出了一种连接和聚集操作的新算法JAMDHBJI，该算法充分考虑了ROLAP中复杂多维层次的特点，同时考虑到并非全部维都具有维层次的语义特性，将维层次编码和位图连接索引有效结合，把复杂的连接和分组聚集操作转化为在事实表上的区域查询，从而大大提高了连接和分组聚集的效率。理论分析表明该算法是高效的。