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

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

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

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