面向復(fù)雜距離度量的MapReduce相似性連接技術(shù)研究.pdf

1、相似性連接操作在網(wǎng)頁副本檢測、實體識別、數(shù)據(jù)清洗和圖像檢索等領(lǐng)域都有很廣泛的應(yīng)用，隨著數(shù)據(jù)規(guī)模的不斷增大，利用分布式并行框架處理大規(guī)模數(shù)據(jù)的相似性連接已經(jīng)吸引了越來越多的科研工作者和商業(yè)公司的關(guān)注。而EMD(Earth Mover's Distance)和Bregman Divergence等復(fù)雜距離度量因較強(qiáng)的魯棒性及相似性度量結(jié)果更符合人類視覺等原因，被廣泛應(yīng)用于度量圖像及語音等類型數(shù)據(jù)的相似性，但現(xiàn)有的關(guān)于上述復(fù)雜距離度量的相似性

2、連接算法多只適用于集中式環(huán)境，無法滿足大規(guī)模數(shù)據(jù)的處理需求，因此本文研究了利用MapReduce分布式并行處理框架解決面向復(fù)雜距離度量的大規(guī)模數(shù)據(jù)相似性連接的問題。
　　首先基于塊嵌套循環(huán)思想，使用隨機(jī)均勻的數(shù)據(jù)劃分方式，提出了MapReduce框架下基本的EMD-BNLJ算法和Breg-BNLJ算法，其中EMD-BNLJ算法可解決面向EMD距離的大規(guī)模數(shù)據(jù)Top-k相似性自連接問題，Breg-BNLJ算法可解決面向Bregman

3、 Divergence距離的大規(guī)模數(shù)據(jù)相似性連接問題。
　　其次根據(jù)EMD距離對偶問題的特性，將原始數(shù)據(jù)映射到一維空間，之后設(shè)計了基于一維空間內(nèi)數(shù)據(jù)位置局部性的數(shù)據(jù)劃分策略，減少了不必要的通信開銷，并通過采樣估算計算代價設(shè)計了基于Quantile的負(fù)載均衡策略，保證了算法的負(fù)載均衡性，進(jìn)而提出了面向EMD距離的大規(guī)模數(shù)據(jù)Top-k EMD-DLPJ相似性自連接算法。在真實數(shù)據(jù)集上進(jìn)行的豐富實驗證實，EMD-DLPJ算法的通信開銷最

4、多為EMD-BNLJ算法的1/5，而執(zhí)行效率最高為EMD-BNLJ算法的6.9倍。
　　最后利用Bregman Divergence距離計算的特點，設(shè)計了以VA-File分割原始數(shù)據(jù)空間的數(shù)據(jù)劃分策略，可提前過濾掉不必要的距離計算，減少通信開銷，進(jìn)一步通過采樣估算計算代價設(shè)計了基于前綴的數(shù)據(jù)分組策略，保證了算法的負(fù)載均衡性，進(jìn)而提出了面向Bregman Divergence距離的大規(guī)模數(shù)據(jù)Breg-VAFJ相似性連接算法。在多種真

5、實數(shù)據(jù)集上的大量實驗證實，Breg-VAFJ算法的通信開銷最多為Breg-BNLJ算法的1/3，而執(zhí)行效率最高為Breg-BNLJ算法的4.8倍。
　　本文研究了面向復(fù)雜距離度量EMD和Bregman Divergence的基于MapReduce的相似性連接技術(shù)，根據(jù)各距離的計算特性設(shè)計了可精確控制的針對原始數(shù)據(jù)集的數(shù)據(jù)劃分方法，取代了基本的隨機(jī)均勻劃分方法，減少了MapReduce作業(yè)的通信開銷。同時通過采樣估算計算代價，設(shè)計了