李立现　屈晓平　高琴琴

摘要：大数据主要有四个典型特征：海量、多样性、高速、易变。连接算法优化是大数据热点问题之一，2010年以来，数据库顶级会议ICDE，Sigmod和VLDB每年都有专门的文章研究基于MapReduce的连接算法优化。依据连接条件主要可以分为等值连接法、数据倾斜时连接法和任意连接法，分析三种数据连接方法，介绍三种连接算法设计和优化方式，并针对基于BloomFilter等值连接设计和优化做了和二阶段法和三阶段法的实验分析。两表等值连接，数据量较大时，采用基于BloomFilter等值连接方式会在一定范围减少算法执行时间，提高数据连接效率。

关键词：云计算；大数据集；等值连接；任意连接

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）13-0219-02

Abstract： Big data mainly has four typical characteristics： mass， diversity， high speed， easy to change.Connection algorithm optimization is one of the big data issues， since 2010， the database top meeting ICDE Sigmod and VLDB every year have special article studies connection efficiency optimization algorithm based on graphs.According to the connecting conditions are equivalent connecting method， the data skew links and any link method， analyzes the three methods of data connection， introduce three kinds of connection algorithm design and optimization method， and based on BloomFilter contour connection design and optimization done and two stage method and experimental analysis of three phase method.Equal join two tables， large amount of data， based on BloomFilter equivalent connections will be reduced in a certain range algorithm execution time， improve the efficiency of data connection.

Key words： Cloud Computing； Big Data ； Equi-join； [θ]Join

根据参考材料[1]中统计显示全部企业的信息每天高达 2.2ZB存储量，其中大型企业平均每天可以产生10WTB的信息量，而中小企业平均每天可以产生 563TB 的数据量。大数据主要有四个典型特征：海量、多样性、高速、易变[1-5]。连接算法优化是大数据热点问题之一，2010年以来，数据库顶级会议ICDE，Sigmod和VLDB每年都有专门的文章研究基于MapReduce的连接算法效率优化[6-10]。研究基于MapReduce的连接算法并优化其效率是大数据在云平台下能够快速处理的关键。依据连接条件，目前主要连接算法主要体现在以下三个方面：等值连接算法的设计与优化，数据倾斜时的连接算法的设计与优化，任意连接算法的设计与优化[11-15]。

1 大数据集连接算法

近年来，大数据领域中最常用的一个并行框架是MapReduce，MapReduce为许多大型公司尤其是互联网公司处理业务需求，基于MapReduce设计的Hive是现在市场主流的分布式数据仓库[14]。……