基于MapReduce的大數(shù)據(jù)連接算法的設計與優(yōu)化.pdf

1、近年來，隨著互聯(lián)網(wǎng)技術的廣泛普及，以博客、社交網(wǎng)絡等為代表的新型應用得到了廣泛使用，同時伴隨著云計算等技術的飛速發(fā)展，互聯(lián)網(wǎng)中的數(shù)據(jù)正以前所未有的速度增長和積累，大數(shù)據(jù)已經(jīng)走入我們的生活。
　　2004年Google提出的MapReduce并行編程環(huán)境，已經(jīng)在大數(shù)據(jù)處理領域得到了廣泛的應用。Yahoo!，F(xiàn)acebook，Amazon等大型互聯(lián)網(wǎng)公司都紛紛應用MapReduce來處理大數(shù)據(jù)相關問題，同時，學術界也對MapReduc

2、e的相關算法做出了巨大貢獻，有效地推動了MapReduce的發(fā)展。
　　本文在深入研究和總結相關領域已有成果的基礎上，圍繞基于MapReduce的數(shù)據(jù)連接算法效率優(yōu)化問題，主要開展了以下的研究工作:
　　首先，本文提出了基于MapReduce的Maxdiff直方圖的高效建立算法，包括準確算法和近似算法。Maxdiff直方圖可以準確地評估數(shù)據(jù)集內(nèi)的數(shù)據(jù)分布情況，例如可以提供數(shù)據(jù)傾斜的情況或者數(shù)據(jù)集之間連接屬性的連接選擇率等重要

3、信息，為后文連接算法的優(yōu)化做了一個基礎工作。
　　其次，本文提出了基于BloomFilter的等值連接算法，核心思想是利用BloomFilter減少map和reduce之間網(wǎng)絡傳輸量從而提高等值連接算法的效率。為此，首先提出了基于MapReduce的BloomFilter高效建立算法;其次提出了基于BloomFilter的等值連接算法，包括兩表等值連接和多表等值連接;最后基于磁盤I/O和網(wǎng)絡I/O建立了等值連接算法代價模型，用以選

4、擇基于MapReduce的最優(yōu)等值連接效率方案。
　　再次，本文提出了針對數(shù)據(jù)傾斜的兩表等值連接算法和多表等值連接算法。針對兩表等值連接，優(yōu)化了數(shù)據(jù)集中的一個或者幾個數(shù)據(jù)出現(xiàn)過多時的連接算法效率。對于多表等值連接，采用基于值域分區(qū)(range partition)的方法，優(yōu)化了用一輪MapReduce任務完成數(shù)據(jù)傾斜的多表連接算法效率。
　　最后，本文提出了基于MapReduce的多表任意連接算法。首先提出了用一輪MapRe

5、duce來完成多表任意連接算法(SEJ)，核心思想是利用拉格朗日乘法來最優(yōu)化網(wǎng)絡傳輸量，同時采用隨機化方法保證reduce端的負載均衡;然后基于算法SEJ和多表連接算法的代價模型，提出了一個動態(tài)規(guī)劃算法生成基于MapReduce的多表任意連接的最優(yōu)化連接方案。
　　本文從基于MapReduce的大數(shù)據(jù)連接算法效率優(yōu)化問題出發(fā)，圍繞著等值連接算法效率優(yōu)化，數(shù)據(jù)傾斜的連接算法效率優(yōu)化和θ連接算法效率優(yōu)化問題進行研究，提出的算法能夠有效