本文關(guān)鍵詞：面向復(fù)雜距離度量的MapReduce相似性連接技術(shù)研究

  更多相關(guān)文章： 相似性連接 復(fù)雜距離 MapReduce 數(shù)據(jù)劃分 負載均衡

【摘要】：相似性連接操作在網(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ù)雜距離度量因較強的魯棒性及相似性度量結(jié)果更符合人類視覺等原因,被廣泛應(yīng)用于度量圖像及語音等類型數(shù)據(jù)的相似性,但現(xiàn)有的關(guān)于上述復(fù)雜距離度量的相似性連接算法多只適用于集中式環(huán)境,無法滿足大規(guī)模數(shù)據(jù)的處理需求,因此本文研究了利用MapReduce分布式并行處理框架解決面向復(fù)雜距離度量的大規(guī)模數(shù)據(jù)相似性連接的問題。首先基于塊嵌套循環(huán)思想,使用隨機均勻的數(shù)據(jù)劃分方式,提出了MapReduce框架下基本的EMD-BNLJ算法和Breg-BNLJ算法,其中EMD-BNLJ算法可解決面向EMD距離的大規(guī)模數(shù)據(jù)Top-k相似性自連接問題,Breg-BNLJ算法可解決面向Bregman Divergence距離的大規(guī)模數(shù)據(jù)相似性連接問題。其次根據(jù)EMD距離對偶問題的特性,將原始數(shù)據(jù)映射到一維空間,之后設(shè)計了基于一維空間內(nèi)數(shù)據(jù)位置局部性的數(shù)據(jù)劃分策略,減少了不必要的通信開銷,并通過采樣估算計算代價設(shè)計了基于Quantile的負載均衡策略,保證了算法的負載均衡性,進而提出了面向EMD距離的大規(guī)模數(shù)據(jù)Top-k EMD-DLPJ目似性自連接算法。在真實數(shù)據(jù)集上進行的豐富實驗證實,EMD-DLPJ算法的通信開銷最多為EMD-BNLJ算法的1/5,而執(zhí)行效率最高為EMD-BNLJ算法的6.9倍。最后利用Bregman Divergence距離計算的特點,設(shè)計了以VA-File分割原始數(shù)據(jù)空間的數(shù)據(jù)劃分策略,可提前過濾掉不必要的距離計算,減少通信開銷,進一步通過采樣估算計算代價設(shè)計了基于前綴的數(shù)據(jù)分組策略,保證了算法的負載均衡性,進而提出了面向Bregman Divergence距離的大規(guī)模數(shù)據(jù)Breg-VAFJ相似性連接算法。在多種真實數(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ù)劃分方法,取代了基本的隨機均勻劃分方法,減少了MapReduce作業(yè)的通信開銷。同時通過采樣估算計算代價,設(shè)計了對應(yīng)的負載均衡策略,有效地保證了MapReduce作業(yè)的負載均衡性。最終在多個真實數(shù)據(jù)集上的大量實驗證實了本文提出的算法的高效性。
【關(guān)鍵詞】：相似性連接 復(fù)雜距離 MapReduce 數(shù)據(jù)劃分 負載均衡
【學位授予單位】：東北大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP338.6;TP391.41
【目錄】：

• 摘要5-7
• Abstract7-11
• 第1章 引言11-19
• 1.1 研究背景11-14
• 1.1.1 相似性連接11-12
• 1.1.2 基于復(fù)雜距離的相似性度量12-13
• 1.1.3 大規(guī)模數(shù)據(jù)的分布式并行處理13-14
• 1.2 問題提出14-16
• 1.2.1 基于復(fù)雜距離度量的大規(guī)模數(shù)據(jù)相似性連接的特點14-15
• 1.2.2 研究現(xiàn)狀15-16
• 1.3 本文貢獻16-17
• 1.4 組織結(jié)構(gòu)17-19
• 第2章 相關(guān)工作19-33
• 2.1 復(fù)雜距離相似性度量19-21
• 2.1.1 EMD距離19-20
• 2.1.2 Bregman Divergence度量20-21
• 2.2 索引與數(shù)據(jù)劃分21-25
• 2.2.1 面向EMD距離的索引22-23
• 2.2.2 面向Bregman Divergence的索引23-25
• 2.3 MapReduce計算框架與Hadoop系統(tǒng)25-27
• 2.4 MapReduce計算框架下的相似性連接技術(shù)27-31
• 2.4.1 利用二維空間網(wǎng)格劃分數(shù)據(jù)27-28
• 2.4.2 利用Voronoi圖劃分數(shù)據(jù)28-29
• 2.4.3 利用Z-value空間填充曲線劃分數(shù)據(jù)29-31
• 2.5 本章小結(jié)31-33
• 第3章 基于EMD距離的Top-k相似性連接算法33-55
• 3.1 協(xié)同過濾框架33-36
• 3.1.1 B~+樹過濾34-35
• 3.1.2 LB_(IM)過濾35-36
• 3.1.3 三角不等性過濾36
• 3.2 基于塊嵌套循環(huán)進行數(shù)據(jù)劃分的基本算法36-42
• 3.2.1 抽樣確定Top-k相似性連接初始閾值38-39
• 3.2.2 查找局部S_(Topk)39-42
• 3.3 基于數(shù)據(jù)局部性進行數(shù)據(jù)劃分的改進算法42-49
• 3.3.1 抽樣確定近似分位數(shù)和T值44-45
• 3.3.2 利用數(shù)據(jù)局部性查找局部S_(Topk)45-49
• 3.4 實驗結(jié)果及分析49-53
• 3.5 本章小結(jié)53-55
• 第4章 基于Bregman Divergence度量的相似性連接算法55-77
• 4.1 基于塊嵌套循環(huán)進行數(shù)據(jù)劃分的基本算法55-57
• 4.2 基于VA-File進行數(shù)據(jù)劃分的改進算法57-68
• 4.2.1 構(gòu)建VA-File索引58-59
• 4.2.2 制定負載均衡策略59-66
• 4.2.3 實現(xiàn)相似性連接66-68
• 4.3 實驗結(jié)果及分析68-74
• 4.4 本章小結(jié)74-77
• 第5章 總結(jié)與展望77-79
• 5.1 本文的主要貢獻與結(jié)論77-78
• 5.2 未來工作78-79
• 參考文獻79-83
• 致謝83-85
• 攻讀碩士學位期間的論文項目情況85

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前4條

1 郝建柏;陳賢富;黃雙福;楊俊;;一種基于模糊近鄰標簽傳遞的半監(jiān)督分類算法[J];微電子學與計算機;2010年02期

2 余海洋;林琛;陳珂;江弋;鄒權(quán);;Pass-Join-K:多分段匹配的相似性連接算法[J];計算機科學與探索;2013年10期

3 劉雪莉;王宏志;李建中;高宏;;實體數(shù)據(jù)庫中多相似連接順序選擇策略[J];計算機科學與探索;2012年10期

4 ;[J];;年期

中國碩士學位論文全文數(shù)據(jù)庫 前4條

1 雷斌;面向復(fù)雜距離度量的MapReduce相似性連接技術(shù)研究[D];東北大學;2014年

2 劉雪莉;基于實體的相似性連接操作的研究[D];哈爾濱工業(yè)大學;2012年

3 周健雯;異質(zhì)網(wǎng)絡(luò)上的自相似性連接算法研究與實現(xiàn)[D];復(fù)旦大學;2013年

4 徐媛媛;基于MapReduce的相似性連接研究[D];寧波大學;2014年

，

本文編號：1062810