基于MapReduce的不等式連接預(yù)處理方法的研究.pdf

1、隨著互聯(lián)網(wǎng)的發(fā)展與普及，傳統(tǒng)的數(shù)據(jù)庫(kù)技術(shù)已不能滿足海量數(shù)據(jù)分析處理的新要求。連接是數(shù)據(jù)分析的重要手段，對(duì)大規(guī)模數(shù)據(jù)進(jìn)行預(yù)處理，可以減少連接時(shí)不必要的處理開銷。然而現(xiàn)有的基于MapReduce的連接預(yù)處理需要對(duì)數(shù)據(jù)集進(jìn)行多次遍歷，對(duì)于大規(guī)模數(shù)據(jù)集而言磁盤的開銷很大，其更適合于對(duì)等式連接進(jìn)行預(yù)處理，因此不能滿足不等式連接預(yù)處理的需要。
　　基于MapReduce的不等式連接預(yù)處理方法（PPM），只需要對(duì)數(shù)據(jù)集進(jìn)行一次讀取并分析，可以減

2、少不等式連接map階段的輸出，從而節(jié)省網(wǎng)絡(luò)通信的數(shù)據(jù)量。PPM方法結(jié)合MapReduce編程模型的特點(diǎn)，在預(yù)處理的map階段統(tǒng)計(jì)每個(gè)數(shù)據(jù)塊的連接屬性值的范圍，在reduce階段得到各個(gè)數(shù)據(jù)集連接屬性的最小值和最大值，并根據(jù)它們的大小關(guān)系生成過濾狀態(tài)表，并得到相應(yīng)的過濾區(qū)間。在不等式連接的map階段，忽略不符合過濾區(qū)間范圍的記錄，只傳輸符合條件的記錄。同時(shí)，設(shè)計(jì)了基于集群感知的任務(wù)分配方法，根據(jù)不等式連接的開銷模型和集群環(huán)境對(duì)任務(wù)完成效率

3、的影響，得到一個(gè)當(dāng)前環(huán)境下使得開銷模型最小的Reduce任務(wù)數(shù)量。
　　實(shí)驗(yàn)結(jié)果表明，相比于沒有引入預(yù)處理方法的不等式連接的處理時(shí)間，預(yù)處理方法的額外開銷在4％之內(nèi)；與基于直方圖統(tǒng)計(jì)的M-Bucket-I算法相比較，使用基于PPM的1-Bucket-Theta算法的不等式連接作業(yè)的完成時(shí)間平均降低了34％。預(yù)處理方法在數(shù)據(jù)集的交集不為全集的情況下，能有效地過濾冗余數(shù)據(jù)；在數(shù)據(jù)集之間交集為空的情況下能直接節(jié)省整個(gè)不等式連接作業(yè)的開銷