非均匀数据分布下的MapReduce连接查询算法优化

MapReduce分布式计算框架有助于提升大规模数据连接查询的效率,但当连接属性分布不均匀时,其简单的散列策略容易导致计算节点间负载不均衡,影响作业的整体性能。针对连接查询操作中的数据倾斜问题,研究了MapReduce框架下大规模数据连接查询操作的优化算法。首先对经典的改进重分区连接查询算法进行实验分析,研究了传统MapReduce计算框架下连接查询操作的执行流程,找出了基于MapReduce计算框架的连接查询算法在数据分布不均匀时的性能瓶颈;进而提出了组合分割平衡分区优化策略,设计并实现了基于组合分割平衡分区优化策略的改进型连接查询算法。实验结果表明,提出的优化策略在大规模数据的连接查询处理上很好地解决了数据倾斜带来的性能影响,具有好的时间性能和可扩展性。     

利用快速无偏分层图抽样算法的MapReduce负载平衡方法

提出一种基于快速无偏分层图抽样的MapReduce负载平衡方法.将聚类算法融合到MapReduce连接操作中,提出MapReduce并行聚类连接算法的实现方法;根据聚类结果动态调整抽样率的无偏分层图抽样算法,从而实现连接操作目标数据的准确、平衡抽样.通过合成数据集和真实数据集下的数据处理实验,与Hash连接算法及基于NS抽样的聚类算法进行对比,验证了所提出的算法方案在不同数据倾斜程度下都具有良好的负载平衡性能,其运行效率也没有因为新采样算法的采用而受到影响.     

数据倾斜情况下基于MapReduce模型的连接算法研究

基于MapReduce的连接算法的研究是海量数据研究领域的一个重要内容,但都集中在数据分布均匀的情况下进行算法优化,而在实际应用中数据分布往往是不均匀的。本文基于此背景,提出一种适合在数据严重倾斜时使用基于MapReduce编程模型的连接算法Skew Control Join,算法通过采样获取数据集的整体分布,通过全局分区将数据集进行分割,使倾斜数据的处理平均分配到所有的Reduce任务上。实验表明在数据倾斜时,本文提出的算法具有良好的性能,达到研究目标。     

基于MapRed uce的增量式数据集的相似性连接

相似性连接,即利用相似函数度量数据之间的相似程度,满足条件后进行连接操作。MapReduce框架下已存在很多相似性连接算法,但仍然存在一些不足,如大量的索引加大时间、空间的开销;现有算法不能有效地完成增量式数据集的相似性连接等。针对海量增量式数据集进行了研究,采用抽样技术得到有效中枢,形成更为合理的分区,建立分区索引和分配原则,完成新增数据的相似性连接操作。实验证明,该算法能够有效地解决海量增量式数据集的相似性连接问题,验证了分区索引的建立,可以提高新增数据的相似性连接操作的效率。     

MapReduce中连接负载均衡优化研究

数据分析和处理是大规模分布式数据处理应用中的重要任务。由于简单易用和具有灵活性, MapReduce编程模型逐渐成为大规模分布式数据处理系统（如Hadoop系统）的核心模型。由于所处理的数据可能不是均匀分布的,MapReduce编程模型在处理连接操作时,会出现数据倾斜问题。数据倾斜问题严重降低了MapReduce执行连接操作的效率。针对MapReduce中连接操作的数据倾斜问题,分析了造成MapReduce连接性能瓶颈的原因并建立负载均衡代价模型,提出了用范围分割方法控制连接过程中的数据倾斜问题实现负载均衡的策略。实验结果表明,所提方法明显提高了连接的效率。     

基于MapReduce与相关子空间的局部离群数据挖掘算法

针对高维海量数据,在MapReduce编程模型下,提出了一种基于相关子空间的局部离群数据挖掘算法.该算法首先利用属性维上的局部稀疏程度,重新定义了相关子空间,从而能够有效地刻画各种局部数据集上的分布特征;其次,利用局部数据集的概率密度,给出了相关子空间中的局部离群因子计算公式,有效地体现了相关子空间中数据对象不服从局部数据集分布特征的程度,并选取离群程度最大的N个数据对象定义为局部离群数据;在此基础上,采用LSH分布式策略,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.     

基于Hadoop二阶段并行模糊c-Means数据聚类算法

为了解决MapReduce机制下算法通信时间占用比过高实际应用价值受限的问题,提出了基于Hadoop二阶段并行c-Means聚类算法;首先,采用成员管理协议方式实现成员管理与MapReduce降低操作的同步化方法,改进MapReduce机制下的MPI通讯管理方法;其次,实行典型个体组降低操作代替全局个体降低操作,并定义二阶段缓冲算法,通过第一阶段的缓冲进一步降低第二阶段MapReduce操作的数据量,尽可能降低大数据带来的对算法负面影响;通过仿真实验表明该算法在处理大数据上的性能表现较为优异;该算法在大规模数据集上的并行率和加速比都优于小型数据集上的表现,说明了该算法能够实时根据数据量的大小对自身进行调整。     

基于索引偏移的MapReduce聚类负载均衡策略

MapReduce作为一种分布式编程模型,被广泛应用于大规模和高维度数据集的处理中。其采用原始Hash函数 划分 数据,当数据分布不均匀时,常会出现数据倾斜的问题。基于MapReduce的聚类算法,需要多次迭代且不清楚各阶段Reduce的输入数据分布,因此现有的解决数据倾斜的方法并不适用。为解决数据划分的不均衡问题,提出一种当存在数据倾斜时更改剩余分区索引的策略。该方法在Map运行的过程中统计将要分给各reducer的数据量,由JobTrackcr监控全局的分区信息并根据数据倾斜模型动态修改原分区函数;在接下来的分区过程中,Partitioner把即将导致倾斜的分区索引到其余负载较轻的reducer上,使各节点的负载达到均衡。基于Zipf分布数据集和真实数据集,将所提算法与现有的解决数据倾斜的方法进行对比,结果证明,所提策略解决了MapReduce聚类中的数据倾斜问题,且在稳定性与执行时间上优于Hash和基于采样的动态分区法。     

一种基于MapReduce的局部相似自连接算法

局部相似自连接能在给定的单个数据集中快速找到所有满足相似要求的记录对,它在数据清洗、基因序列比对和剽窃检测等领域都有广泛的应用。为研究基于单个字符串集的并行自连接算法,提出了一种基于MapReduce框架的自连接算法,解决了局部相似自连接的定位问题。该算法采用了过滤验证二阶段模式;在过滤阶段,采用无关对过滤和冗余对过滤抛弃了大量的无效字符串对;在验证阶段,通过生成小编号串内容保留项解决了字符串编号和内容的快速配对问题。实验结果显示,该算法在大数据集上的自连接速度一直快于当前的优秀算法LS-Join,同时非常适合动态编辑距离参数环境下的局部相似自连接操作。实验结果也证明,该算法中提出的相关技术有效地提高了局部相似自连接的速度。     

基于列存储的MapReduce并行连接算法

针对传统关系型数据库在对大数据进行操作时,系统性能严重下降、计算效率提升有限以及可扩展性差等问题,引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce并行连接算法。设计面向大数据的分布式计算模型,包括MapReduce分布式环境下的列存储文件格式MCF,采用协同定位策略实现对分布式存储的优化。使用分片聚集和子连接启发式优化方法,实现大数据在MapReduce分布式环境下并行连接算法。实验结果证明,在大数据分析处理中,该算法在执行时间和负载能力上有着较好的优化性能,同时具有良好的可扩展性。     

MapReduce连接查询的I/O代价研究

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而MapReduce是一种用于大规模数据集并行处理的编程模型,研究基于MapReduce的连接查询代价评估和查询优化,有着学术意义和应用价值.MapReduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于MapReduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.     

Fast and scalable vector similarity joins with MapReduce

Vector similarity join, which finds similar pairs of vector objects, is a computationally expensive process. As its number of vectors increases, the time needed for join operation increases proportional to the square of the number of vectors. Various filtering techniques have been proposed to reduce its computational load. On the other hand, MapReduce algorithms have been studied to manage large datasets. The recent improvements, however, still suffer from its computational time and scalability. In this paper, we propose a MapReduce algorithm FACET(FAst and sCalable maprEduce similariTy join) to efficiently solve the vector similarity join problem on large datasets. FACET is an all-pair exact join algorithm, composed of two stages. In the first stage, we use our own novel filtering techniques to eliminate dissimilar pairs to generate non-redundant candidate pairs. The second stage matches candidate pairs with the vector data so that similar pairs are produced as the output. Both stages employ parallelism offered by MapReduce. The algorithm is currently designed for cosine similarity and Self Join case. Extensions to other similarity measures and R-S Join case are also discussed. We provide the I/O analysis of the algorithm. We evaluate the performance of the algorithm on multiple real world datasets. The experiment results show that our algorithm performs, on average, 40 % upto 800 % better than the previous state-of-the-art MapReduce algorithms.     

基于Fermi架构的Join算法

在列数据库中,连接操作依然是最核心和最耗时的操作,GPU强大的计算能力可为此提供新的优化手段。基于Fermi架构,提出了新的Hash Join算法和Sort merge Join算法,其基本思想是充分利用该架构新增的缓存结构来减少连接操作的cache缺失率。与CUDA stream技术相结合,新算法在输出结果较多时可以有效地隐藏主存与显存间数据传输带来的延迟,进一步提升其执行效率。实验结果证实了基于Fcrmi架构的Hash Join算法处理偏抖数据的高效性及Sort merge Join算法的稳定性,并且通过比较表明,这两种算法的性能全面优于基于多核CPU充分优化的Join算法,最大加速2.4倍,在外键分布高偏抖时新的Hash Join算法的执行速度甚至达到每秒217M元组。     

基于数据流的k-近邻连接算法

k-近邻连接查询是空间数据库中一种常用的操作,该查询处理过程涉及连接和最近邻查询两个复杂操作.传统的集中式k-近邻连接查询算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-近邻连接查询算法成为了目前亟需解决的问题.现有的分布式k-近邻连接查询算法都包括了多轮串行的MapReduce任务,而每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此算法效率低下.首先提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模.在该框架基础上,提出了一种高效的k-近邻连接算法,它利用空间填充曲线将多维数据映射为一维数据,从而将k-近邻连接查询转化为一维范围查询.实验结果表明,该算法的可扩展性较高,且效率比现有算法更优.     

基于直方图的并行结构连接算法

连接操作是最昂贵且常用的数据库操作．在传统数据库系统中，主要的连接操作是等值连接操作，因此，传统的并行连接算法主要集中于并行等值连接操作．另外，随着XML在Web应用中变得越来越重要，XML已经成为Internet上一种新的数据交换标准．对XML数据的连接操作不同于传统数据库中的等值连接操作，它属于结构连接操作．以前适合等值连接操作的并行连接算法并不能有效地解决结构连接问题．因此，第1次提出了并行结构连接问题，并且通过应用直方图的思想于并行连接中，从而提出两种基本的并行XML结构连接算法、等高直方图连接算法和等宽直方图连接算法．实验表明这两种算法具有较好的性能．     

Set similarity join on massive probabilistic data using MapReduce

In this paper, we focus on set similarity join on massive probabilistic data using MapReduce, there is no effective approach that can process this problem efficiently. MapReduce is a popular paradigm that can process large volume data more efficiently, in this paper, we proposed two approaches using MapReduce to deal with this task: Hadoop Join by Map Side Pruning and Hadoop Join by Reduce Side Pruning. Hadoop Join by Map Side Pruning uses the sum of the existence probability to filter out the probabilistic sets directly at the Map task side which have no any chance to be similar with any other probabilistic set. Hadoop Join by Reduce Side Pruning uses probability sum based pruning principle and probability upper bound based pruning principle to reduce the candidate pairs at Reduce task side, it can save the comparison cost. Based on the above approaches, we proposed a hybrid solution that employs both Map-side and Reduce-side pruning methods. Finally we implemented the above approaches on Hadoop-0.20.2 and performed comprehensive experiments to their performance, we also test the speedup ratio compared with the naive method: Block Nested Loop Join. The experiment results show that our approaches have much better performance than that of Block Nested Loop Join and also have good scalability. To the best of our knowledge, this is the first work to try to deal with set similarity join on massive probabilistic data problem using MapReduce paradigm, and the approaches proposed in this paper provide a new way to process the massive probabilistic data.     

Handling data skew in join algorithms using MapReduce

One of the major obstacles hindering effective join processing on MapReduce is data skew. Since MapReduce’s basic hash-based partitioning method cannot solve the problem properly, two alternatives have been proposed: range-based and randomized methods. However, they still remain some drawbacks: the range-based method does not handle join product skew, and the randomized method performs worse than the basic hash-based partitioning when input relations are not skewed. In this paper, we present a new skew handling method, called multi-dimensional range partitioning (MDRP). The proposed method overcomes the limitations of traditional algorithms in two ways: 1) the number of output records expected at each machine is considered, which leads to better handling of join product skew, and 2) a small number of input records are sampled before the actual join begins so that an efficient execution plan considering the degree of data skew can be created. As a result, in a scalar skew experiment, the proposed join algorithm is about 6.76 times faster than the range-based algorithm when join product skew exists and about 5.14 times than the randomized algorithm when input relations are not skewed. Moreover, through the worst-case analysis, we show that the input and the output imbalances are less than or equal to 2. The proposed algorithm does not require any modification to the original MapReduce environment and is applicable to complex join operations such as theta-joins and multi-way joins.     

Join processing with threshold-based filtering in MapReduce

Data analytics, in particular those involving heterogeneous data, often require join operations on datasets collected from different sources. MapReduce, one of the most popular frameworks for large-scale data processing, is not suited for joining multiple datasets. This is because MapReduce often produces a large number of redundant intermediate results, irrespective of the size of the joined records. Although several existing approaches attempt to reduce the number of such redundant results using Bloom filters, they may be inefficient if large portions of records are joined or the number of distinct keys is large. To alleviate this problem, we propose a join processing method with threshold-based filtering in MapReduce, called TMFR-Join, which is an abbreviation for “Threshold-based Map-Filter-Reduce Join”. TMFR-Join applies filters according to their performance, which is estimated in terms of false-positive rates. It also provides a general framework for exploiting various filtering techniques that support certain desired operations. The experimental results indicate that the performance of TMFR-Join is close to that of the better of existing join processing techniques, both with and without filters.     

Join and data redistribution algorithms for hypercubes

An important aspect of database processing in parallel computer systems is the use of data parallel algorithms. Several parallel algorithms for the relational database join operation in a hypercube multicomputer system are given. The join algorithms are classified as cycling or global partitioning based on the tuple distribution method employed. The various algorithms are compared under a common framework, using time complexity analysis as well as an implementation on a 64-node NCUBE hypercube system. In general, the global partitioning algorithms demonstrate better speedup. However, the cycling algorithm can perform better than the global algorithms in specific situations, viz., when the difference in input relation cardinalities is large and the hypercube dimension is small. The usefulness of the data redistribution operation in improving the performance of the join algorithms, in the presence of uneven data partitions, is examined. The results indicate that redistribution significantly decreases the join algorithm execution times for unbalanced partitions     

概率数据上基于EMD距离的并行Top-k相似性连接算法

以无线传感器网络为代表的新型数据应用和以图像处理为基础的传统数据应用都产生了大规模的概率数据.在概率数据的管理中,Top-k相似性连接操作返回最相似的k 对概率数据,具有重要应用价值.直方图是最常用的概率数据模型之一,而EMD（Earth Mover’s Distance）距离因其较强的鲁棒性可更准确地量化直方图概率数据之间的相似性.然而EMD距离的计算却具有三次方的时间复杂度,给基于EMD距离的Top-k 相似性连接带来巨大挑战.基于流行的MapReduce并行处理框架,利用EMD距离对偶线性规划问题的优良特性,提出了两种大规模概率数据上基于EMD距离的Top-k相似性连接算法.首先提出基于块嵌套循环连接思想的基本解决方法,命名为Top-k BNLJ算法.进而改进数据划分策略,提出基于数据局部性进行数据划分的Top-k DLPJ 算法,有效降低了MapReduce作业执行过程中的数据传输量.使用大规模真实数据集对两种算法进行评估,证实了本文提出的Top-k DLPJ算法的高效性和处理大规模数据集时的良好扩展性.