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

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

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

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

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

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