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

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

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

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

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

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