基于MapReduce的相似性連接研究.pdf

1、隨著社會(huì)網(wǎng)絡(luò)、移動(dòng)應(yīng)用及在線服務(wù)等信息技術(shù)的廣泛應(yīng)用和不斷發(fā)展，數(shù)據(jù)呈爆炸式增長(zhǎng)，海量數(shù)據(jù)的分析需要強(qiáng)大的計(jì)算能力。相似性連接作為數(shù)據(jù)分析的一個(gè)基本操作，在相似搜索、數(shù)據(jù)挖掘上它可被用來(lái)大幅度地提高計(jì)算速度，提升計(jì)算效率。相似性連接類似于數(shù)據(jù)庫(kù)連接，不同點(diǎn)在于，相似性連接是針對(duì)不同的數(shù)據(jù)類型，采用相應(yīng)的度量函數(shù)以及閾值限定，通過(guò)函數(shù)度量后再做相應(yīng)的連接操作。
　　單臺(tái)計(jì)算機(jī)的處理能力以及傳統(tǒng)的技術(shù)架構(gòu)已經(jīng)很難滿足海量數(shù)據(jù)處理的計(jì)算

2、要求，但是MapReduce軟件框架的出現(xiàn)為海量數(shù)據(jù)下的相似性連接帶來(lái)了曙光。目前，MapReduce下相似性連接技術(shù)已經(jīng)取得了較好的研究成果，但仍存在一些問(wèn)題：處理速度仍不夠快、處理數(shù)據(jù)類型較單一、不能有效處理動(dòng)態(tài)數(shù)據(jù)等等。針對(duì)數(shù)據(jù)處理速度的問(wèn)題，本文提出了改進(jìn)的基于劃分的算法和改進(jìn)的基于前綴過(guò)濾的算法，可以提高相似性連接的計(jì)算效率。以下是本文的主要研究?jī)?nèi)容：
　　1、采用分而治之的策略，借鑒 QuickJoin算法，本文提出了

3、改進(jìn)的基于劃分的算法（MRSJ_PDS算法），將海量數(shù)據(jù)分解為若干個(gè)規(guī)模較小的數(shù)據(jù)集，并分散至 MapReduce分布式集群上，再進(jìn)行相應(yīng)的相似性連接操作。主要內(nèi)容有：（1）進(jìn)行數(shù)據(jù)的劃分操作之前，對(duì)原始數(shù)據(jù)集進(jìn)行采樣，采用聚類算法計(jì)算出有效的聚類中心（亦即中樞），再根據(jù)有效中樞將原始數(shù)據(jù)集劃分并形成分區(qū)（其大小未超過(guò)單個(gè)節(jié)點(diǎn)上能計(jì)算的塊大?。?。同時(shí)，為了有效并充分利用計(jì)算過(guò)程中產(chǎn)生的數(shù)據(jù)，避免對(duì)數(shù)據(jù)進(jìn)行多次重復(fù)計(jì)算。本文采用索引技術(shù)存

4、儲(chǔ)中間數(shù)據(jù)，即為滿足條件的分區(qū)建立 K-D樹(shù)索引，進(jìn)而獲取所有相似對(duì)。實(shí)驗(yàn)證明，該方法能夠有效減少數(shù)據(jù)的劃分次數(shù)，并有效地降低了相似對(duì)驗(yàn)證的頻率，與之前的算法進(jìn)行比較該算法的運(yùn)行效率有明顯的提升。（2）在現(xiàn)實(shí)世界中廣泛存在著動(dòng)態(tài)數(shù)據(jù)，可以將部分?jǐn)?shù)據(jù)作為原數(shù)據(jù)集上新增數(shù)據(jù)，針對(duì)新增數(shù)據(jù)的相似性操作，本文設(shè)定了相應(yīng)的分配原則，每個(gè)新增數(shù)據(jù)會(huì)進(jìn)入到對(duì)應(yīng)的分區(qū)，最終獲取新增數(shù)據(jù)的相似對(duì)。
　　2、在偵查近重復(fù)網(wǎng)頁(yè)、屏蔽惡意廣告、推薦相似用

5、戶等應(yīng)用中，集合相似性連接技術(shù)被廣泛使用。通常，集合相似性連接技術(shù)采用過(guò)濾-驗(yàn)證這樣的計(jì)算框架，利用前綴過(guò)濾剪枝技術(shù)縮短候選集列表，但是在 MapReduce平臺(tái)下，這樣的算法會(huì)產(chǎn)生大量的候選集，增加相似對(duì)的驗(yàn)證時(shí)間。本文提出了改進(jìn)的基于前綴過(guò)濾的MapReduce相似性連接算法（MR_MinPrefix算法），利用最小前綴過(guò)濾技術(shù)對(duì) token索引列表進(jìn)行更好的剪枝操作，降低候選集生成的代價(jià)，并保存記錄的相關(guān)信息到指定文件中，便于后續(xù)