基于MapReduce的海量數(shù)據(jù)集的相似自連接算法的設(shè)計與實現(xiàn).pdf

1、相似自連接是一個在很多應(yīng)用領(lǐng)域中很重要的問題，廣泛的應(yīng)用于數(shù)據(jù)清洗，文本查重，基于密度的聚類分析等方面。對于海量數(shù)據(jù)集，MapReduce可以提供一個有效的分布式計算框架，對于MapReduce框架下的相似自連接研究工作仍然存在不足，如針對聚集數(shù)據(jù)區(qū)域采用加細劃分方法目的是解決負載平衡問題，但不易實現(xiàn)。并且現(xiàn)有的算法不能有效的完成海量數(shù)據(jù)集的相似自連接操作，存在大量不必要的計算且不適用于高維度的數(shù)據(jù)，因此對海量數(shù)據(jù)集的相似自連接的研究尤

2、為必要。本文主要研究新穎的基于MapReduce的相似自連接新算法，主要有以下兩個方面的內(nèi)容:
　　1.由于已有基于MapReduce的相似自連接MR-DSJ算法，會產(chǎn)生大量的不必要的計算且僅適用于低維度數(shù)據(jù)。針對該問題，本文提出了基于MapReduce的坐標過濾算法。首先對高維數(shù)據(jù)進行降維操作，采用滑動窗口過濾方式來減少候選集的數(shù)量。最后在鄰網(wǎng)格中利用坐標過濾技術(shù)。新的方法避免了不必要距離和重復(fù)計算。實驗結(jié)果表明，我們的方法可以

3、有效的降低算法的時間復(fù)雜度，提高了自連接操作的命中率，并且對于高維度數(shù)據(jù)優(yōu)化效果明顯。
　　2.由于聚集的數(shù)據(jù)會分配到同一個Reducer任務(wù)上，就會出現(xiàn)Reducer處理任務(wù)總數(shù)量不均衡的問題。為了解決這種負載不均衡的問題，本文研究了對聚集數(shù)據(jù)采用內(nèi)切圓算法，內(nèi)切圓內(nèi)數(shù)據(jù)點經(jīng)過過濾，使得聚集數(shù)據(jù)被合理計算。為了數(shù)據(jù)充分的集中在圓內(nèi)進一步減少計算量，本文又提出六邊形的網(wǎng)格劃分方法。實驗結(jié)果表明，我們的方法比其他算法有更高的效率，對