發(fā)布時(shí)間：2017-10-19 19:09

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

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

【摘要】：相似性連接操作在網(wǎng)頁(yè)副本檢測(cè)、實(shí)體識(shí)別、數(shù)據(jù)清洗和圖像檢索等領(lǐng)域都有很廣泛的應(yīng)用,隨著數(shù)據(jù)規(guī)模的不斷增大,利用分布式并行框架處理大規(guī)模數(shù)據(jù)的相似性連接已經(jīng)吸引了越來(lái)越多的科研工作者和商業(yè)公司的關(guān)注。而EMD(Earth Mover's Distance)和Bregman Divergence等復(fù)雜距離度量因較強(qiáng)的魯棒性及相似性度量結(jié)果更符合人類視覺(jué)等原因,被廣泛應(yīng)用于度量圖像及語(yǔ)音等類型數(shù)據(jù)的相似性,但現(xiàn)有的關(guān)于上述復(fù)雜距離度量的相似性連接算法多只適用于集中式環(huán)境,無(wú)法滿足大規(guī)模數(shù)據(jù)的處理需求,因此本文研究了利用MapReduce分布式并行處理框架解決面向復(fù)雜距離度量的大規(guī)模數(shù)據(jù)相似性連接的問(wèn)題。首先基于塊嵌套循環(huán)思想,使用隨機(jī)均勻的數(shù)據(jù)劃分方式,提出了MapReduce框架下基本的EMD-BNLJ算法和Breg-BNLJ算法,其中EMD-BNLJ算法可解決面向EMD距離的大規(guī)模數(shù)據(jù)Top-k相似性自連接問(wèn)題,Breg-BNLJ算法可解決面向Bregman Divergence距離的大規(guī)模數(shù)據(jù)相似性連接問(wèn)題。其次根據(jù)EMD距離對(duì)偶問(wèn)題的特性,將原始數(shù)據(jù)映射到一維空間,之后設(shè)計(jì)了基于一維空間內(nèi)數(shù)據(jù)位置局部性的數(shù)據(jù)劃分策略,減少了不必要的通信開(kāi)銷,并通過(guò)采樣估算計(jì)算代價(jià)設(shè)計(jì)了基于Quantile的負(fù)載均衡策略,保證了算法的負(fù)載均衡性,進(jìn)而提出了面向EMD距離的大規(guī)模數(shù)據(jù)Top-k EMD-DLPJ目似性自連接算法。在真實(shí)數(shù)據(jù)集上進(jìn)行的豐富實(shí)驗(yàn)證實(shí),EMD-DLPJ算法的通信開(kāi)銷最多為EMD-BNLJ算法的1/5,而執(zhí)行效率最高為EMD-BNLJ算法的6.9倍。最后利用Bregman Divergence距離計(jì)算的特點(diǎn),設(shè)計(jì)了以VA-File分割原始數(shù)據(jù)空間的數(shù)據(jù)劃分策略,可提前過(guò)濾掉不必要的距離計(jì)算,減少通信開(kāi)銷,進(jìn)一步通過(guò)采樣估算計(jì)算代價(jià)設(shè)計(jì)了基于前綴的數(shù)據(jù)分組策略,保證了算法的負(fù)載均衡性,進(jìn)而提出了面向Bregman Divergence距離的大規(guī)模數(shù)據(jù)Breg-VAFJ相似性連接算法。在多種真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)證實(shí),Breg-VAFJ算法的通信開(kāi)銷最多為Breg-BNLJ算法的1/3,而執(zhí)行效率最高為Breg-BNLJ算法的4.8倍。本文研究了面向復(fù)雜距離度量EMD和Bregman Divergence的基于MapReduce的相似性連接技術(shù),根據(jù)各距離的計(jì)算特性設(shè)計(jì)了可精確控制的針對(duì)原始數(shù)據(jù)集的數(shù)據(jù)劃分方法,取代了基本的隨機(jī)均勻劃分方法,減少了MapReduce作業(yè)的通信開(kāi)銷。同時(shí)通過(guò)采樣估算計(jì)算代價(jià),設(shè)計(jì)了對(duì)應(yīng)的負(fù)載均衡策略,有效地保證了MapReduce作業(yè)的負(fù)載均衡性。最終在多個(gè)真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)證實(shí)了本文提出的算法的高效性。
【關(guān)鍵詞】：相似性連接 復(fù)雜距離 MapReduce 數(shù)據(jù)劃分 負(fù)載均衡
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：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 問(wèn)題提出14-16
• 1.2.1 基于復(fù)雜距離度量的大規(guī)模數(shù)據(jù)相似性連接的特點(diǎn)14-15
• 1.2.2 研究現(xiàn)狀15-16
• 1.3 本文貢獻(xiàn)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計(jì)算框架與Hadoop系統(tǒng)25-27
• 2.4 MapReduce計(jì)算框架下的相似性連接技術(shù)27-31
• 2.4.1 利用二維空間網(wǎng)格劃分?jǐn)?shù)據(jù)27-28
• 2.4.2 利用Voronoi圖劃分?jǐn)?shù)據(jù)28-29
• 2.4.3 利用Z-value空間填充曲線劃分?jǐn)?shù)據(jù)29-31
• 2.5 本章小結(jié)31-33
• 第3章 基于EMD距離的Top-k相似性連接算法33-55
• 3.1 協(xié)同過(guò)濾框架33-36
• 3.1.1 B~+樹(shù)過(guò)濾34-35
• 3.1.2 LB_(IM)過(guò)濾35-36
• 3.1.3 三角不等性過(guò)濾36
• 3.2 基于塊嵌套循環(huán)進(jìn)行數(shù)據(jù)劃分的基本算法36-42
• 3.2.1 抽樣確定Top-k相似性連接初始閾值38-39
• 3.2.2 查找局部S_(Topk)39-42
• 3.3 基于數(shù)據(jù)局部性進(jìn)行數(shù)據(jù)劃分的改進(jìn)算法42-49
• 3.3.1 抽樣確定近似分位數(shù)和T值44-45
• 3.3.2 利用數(shù)據(jù)局部性查找局部S_(Topk)45-49
• 3.4 實(shí)驗(yàn)結(jié)果及分析49-53
• 3.5 本章小結(jié)53-55
• 第4章 基于Bregman Divergence度量的相似性連接算法55-77
• 4.1 基于塊嵌套循環(huán)進(jìn)行數(shù)據(jù)劃分的基本算法55-57
• 4.2 基于VA-File進(jìn)行數(shù)據(jù)劃分的改進(jìn)算法57-68
• 4.2.1 構(gòu)建VA-File索引58-59
• 4.2.2 制定負(fù)載均衡策略59-66
• 4.2.3 實(shí)現(xiàn)相似性連接66-68
• 4.3 實(shí)驗(yàn)結(jié)果及分析68-74
• 4.4 本章小結(jié)74-77
• 第5章 總結(jié)與展望77-79
• 5.1 本文的主要貢獻(xiàn)與結(jié)論77-78
• 5.2 未來(lái)工作78-79
• 參考文獻(xiàn)79-83
• 致謝83-85
• 攻讀碩士學(xué)位期間的論文項(xiàng)目情況85

【相似文獻(xiàn)】

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

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

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

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

4 ;[J];;年期

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

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

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

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

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

，

本文編號(hào)：1062810