基于MapReduce的相似自連接新方法：過(guò)濾和內(nèi)切圓算法

鮑廣慧 張兆功 李建中,2 玄 萍

1(黑龍江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)2(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)(851890784@qq.com)

?

基于MapReduce的相似自連接新方法：過(guò)濾和內(nèi)切圓算法

鮑廣慧1張兆功1李建中1,2玄 萍1

1(黑龍江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)2(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)(851890784@qq.com)

相似自連接是一個(gè)在很多應(yīng)用領(lǐng)域中很重要的問(wèn)題.對(duì)于海量數(shù)據(jù)集，MapReduce可以提供一個(gè)有效的分布式計(jì)算框架，相似自連接操作也同樣可以應(yīng)用在MapReduce框架下.但已有研究工作仍然存在不足，如對(duì)于聚集數(shù)據(jù)區(qū)域采用加細(xì)劃分方法，目的是負(fù)載平衡，但不易實(shí)現(xiàn).現(xiàn)有的算法不能有效地完成海量數(shù)據(jù)集的相似自連接操作.為此提出了2個(gè)新穎的基于MapReduce的相似自連接算法，其思想是采用坐標(biāo)過(guò)濾技術(shù)，形成有效候選集，以及針對(duì)聚集區(qū)域采用六邊形劃分的內(nèi)切圓算法.過(guò)慮技術(shù)是在等寬網(wǎng)格劃分基礎(chǔ)上，利用同一維坐標(biāo)間的距離差與相似性約束閾值ε進(jìn)行比較，可以明顯地減少候選集的數(shù)量，也證明了六邊形劃分是所有正多邊形全覆蓋中最優(yōu)的劃分方法.實(shí)驗(yàn)結(jié)果表明：新方法比其他算法有更高的效率，提高效率80%以上，它能夠有效地解決有聚集區(qū)域的海量數(shù)據(jù)集的相似自連接問(wèn)題.

海量數(shù)據(jù)集；過(guò)濾；相似自連接；數(shù)據(jù)劃分；Hadoop平臺(tái)；MapReduce編程模型

連接操作(join)是一個(gè)很重要的數(shù)據(jù)庫(kù)操作，相似自連接是join的一種特殊類(lèi)型，即對(duì)同一數(shù)據(jù)類(lèi)型進(jìn)行相似自連接操作.它在數(shù)據(jù)分析中扮演很重要的角色：數(shù)據(jù)清理[1]、相近的文本查重[2]、文件相似性分析[3]和數(shù)據(jù)挖掘等工作，特別在基于密度的聚類(lèi)分析中也用到了相似自連接操作的結(jié)果.大規(guī)模的相似自連接的有效實(shí)現(xiàn)可以加速這些數(shù)據(jù)的分析過(guò)程.本文中，我們主要研究基于MapReduce的海量數(shù)據(jù)集的相似自連接操作.

關(guān)于集合R，S的θ-join的定義為

R??θS=σθ(r,s)={(r,s)|d(r.A,s.A)≤ε}，

(1)

返回結(jié)果為所有的相似對(duì)(r,s)，它們的距離在屬性A上不會(huì)超過(guò)一個(gè)最大閾值ε.ε叫作相似自連接的約束，一般由用戶給定.文中的距離采用歐幾里得距離.

對(duì)于海量數(shù)據(jù)的并行分析與處理，各種各樣的編程模型相繼被開(kāi)發(fā)出來(lái). 從基本的數(shù)據(jù)庫(kù)操作到高水平的數(shù)據(jù)挖掘方法，像聚類(lèi)、分類(lèi)和離群點(diǎn)檢測(cè)[4].由Google提出的MapReduce編程模型以及它在Hadoop上的開(kāi)源實(shí)現(xiàn)受到了廣泛的關(guān)注和使用.

在MapReduce框架下針對(duì)相似自連接的問(wèn)題已有3種方法被提出來(lái).在文獻(xiàn)[4]中，MRDSJ算法被提出，主要利用等寬網(wǎng)格的方法來(lái)減少不必要的距離計(jì)算,可以有效地進(jìn)行數(shù)據(jù)集的相似自連接操作.但是這個(gè)方法不能夠處理聚集的數(shù)據(jù)，需要對(duì)等寬的網(wǎng)格劃分實(shí)行進(jìn)一步加細(xì)劃分，目的是實(shí)現(xiàn)每一個(gè)計(jì)算節(jié)點(diǎn)的負(fù)載平衡.同時(shí)對(duì)于大規(guī)模的數(shù)據(jù)集合，會(huì)產(chǎn)生多余的候選集，嚴(yán)重的影響了算法的效率.為此提出了2個(gè)新的算法——過(guò)濾算法和內(nèi)切圓算法.過(guò)慮算法是在等寬網(wǎng)格劃分基礎(chǔ)上，利用同一維坐標(biāo)間的距離差與約束ε進(jìn)行比較，可以進(jìn)一步減少候選集的數(shù)量.內(nèi)切圓算法是針對(duì)數(shù)據(jù)聚集區(qū)域利用距離的三角不等式，可以快速準(zhǔn)確地計(jì)算出結(jié)果集，避免了每一對(duì)點(diǎn)之間的join運(yùn)算.通過(guò)實(shí)驗(yàn)結(jié)果分析可以看出我們的算法可以減少不必要的計(jì)算，不需要加細(xì)劃分，并且效率有80%的提高.

本文的主要貢獻(xiàn)有3點(diǎn):

1) 我們提出了一個(gè)新的過(guò)濾算法，它在Map-Reduce的框架下來(lái)處理海量數(shù)據(jù)集的相似自連接操作，利用過(guò)濾技術(shù)有效地減少了候選集的數(shù)量.提出了新的降低維數(shù)方法，維度從n維降到2維.

2) 我們提出了一個(gè)新穎的內(nèi)切圓算法，它特別適用于聚集的數(shù)據(jù)集.我們還提出了新奇的正六邊形區(qū)域劃分方法，它使得相鄰點(diǎn)的距離信息被充分的利用，進(jìn)一步提高了內(nèi)切圓算法的效率.我們還證明了正六邊形區(qū)域劃分方法是最優(yōu)的.

3) 應(yīng)用我們的新算法在真實(shí)的生物數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果顯示隨著數(shù)據(jù)量增加，算法執(zhí)行時(shí)間呈現(xiàn)近于線性的增長(zhǎng).

1 相關(guān)工作

相似性連接是一種很重要的操作，目前被大量學(xué)者研究，其中龐俊等人[5]對(duì)相似性連接查詢(xún)技術(shù)做了綜合論述，提出了相似性連接的具體分類(lèi).針對(duì)數(shù)據(jù)類(lèi)型的不同，可分為向量相似性連接、集合相似性連接、字符串相似性連接;按照返回結(jié)果分為所有對(duì)相似性連接、基于閾值的相似性連接、Top-k相似性連接和KNN相似性連接等.

大規(guī)模的海量數(shù)據(jù)的連接操作是一個(gè)計(jì)算代價(jià)很高的操作，隨著數(shù)據(jù)規(guī)模的逐漸增大，如何在分布式的環(huán)境下利用MapReduce并行的執(zhí)行相似性連接操作也引起了研究者們的關(guān)注.在文獻(xiàn)[6]中，馬友忠、孟小峰等人研究了在MapReduce框架下海量高維向量的并行Top-k連接查詢(xún)，主要結(jié)合符號(hào)累計(jì)近似法和基于閾值估計(jì)法，提出了基于SAX的Top-k的連接查詢(xún)算法，返回符合條件的前k個(gè)向量對(duì);文獻(xiàn)[7-8]主要研究在歐幾里得空間上的KNN連接，文獻(xiàn)[8]的作者提出了利用空間填充曲線轉(zhuǎn)換KNN連接在一系列一維范圍內(nèi)搜索的想法，使問(wèn)題轉(zhuǎn)化在基于泰森多邊形法分區(qū)允許一個(gè)有效地連接操作;文獻(xiàn)[8-9]中提出數(shù)據(jù)分區(qū)方法，需要一個(gè)或多個(gè)join操作運(yùn)行在數(shù)據(jù)集合上的連接算法;文獻(xiàn)[10]概述了MapReduce下常見(jiàn)的連接策略;然而，絕大多數(shù)的現(xiàn)有工作關(guān)于并行的連接都采用的是等值連接；Afrati等人[11]提出了優(yōu)化策略對(duì)于多維度的等值連接.但是他們并不能應(yīng)用于相似性連接.廣播的連接策略依賴(lài)于不同屬性的數(shù)據(jù)集之間的操作.它也并不適用于自連接這種相同數(shù)據(jù)集的連接操作;文獻(xiàn)[12]里提到一種有效地相似連接算法用于解決編輯距離約束，它把編輯距離約束轉(zhuǎn)換為2個(gè)字符串間的匹配q-grams的數(shù)量上;文獻(xiàn)[13]對(duì)KNN相似性連接已有方法進(jìn)行了對(duì)比分析;文獻(xiàn)[14]對(duì)多元連接進(jìn)行優(yōu)化，以降低IO代價(jià)為目標(biāo)并針對(duì)MapReduce設(shè)計(jì)一個(gè)并行執(zhí)行策略提高多元連接的性能.

文獻(xiàn)[3]提出利用MapReduce的自連接操作處理稀疏的文件集，采用有效地剪枝策略通過(guò)分區(qū)策略可以克服內(nèi)存的瓶頸，并且提高了效率；針對(duì)大規(guī)模的矢量數(shù)據(jù)的分析，文獻(xiàn)[4]中作者提出在Map-Reduce框架下基于距離的相似自連接.利用數(shù)據(jù)分區(qū)，等寬網(wǎng)格劃分的方法來(lái)減少通信和不必要的距離計(jì)算的數(shù)量，它比較適用于低維度到中維度；他們又繼續(xù)改進(jìn)算法，針對(duì)于高維度的矢量數(shù)據(jù)他們又提出了PHIDJ算法，可以適用于在MapReduce下的并行相似自連接操作[15]；PHIDJ算法主要是利用加細(xì)網(wǎng)格劃分來(lái)處理聚集的數(shù)據(jù)，但不易實(shí)現(xiàn).并且這種方法仍然存在不必要的計(jì)算，針對(duì)聚集區(qū)域的數(shù)據(jù)仍沒(méi)有有效的方法進(jìn)行處理.效率還有待提高，這正是我們要突破的地方，需要進(jìn)一步研究.

1.1 MapReduce框架下的MR-DSJ算法

作為背景介紹，在文獻(xiàn)[4]中，作者提出一個(gè)基于等寬網(wǎng)格劃分的方法.網(wǎng)格中的區(qū)域Cell的寬度是ε正方形(或?qū)τ诟呔S時(shí)Cell是多面體)，如圖1所示，其中一點(diǎn)p的所有join操作的鄰居都在相同的Cell里或者直接相鄰的Cell里，僅規(guī)定相鄰的一部分Cell.這樣和其他Cell中距離的計(jì)算就可以被剪枝掉了.

這種方法很容易用MapReduce來(lái)實(shí)現(xiàn).每個(gè)Reducer只負(fù)責(zé)主Cell中的點(diǎn)，并且計(jì)算主Cell中點(diǎn)的距離和主Cell中點(diǎn)與鄰居Cell中點(diǎn)的距離.通過(guò)減少鄰居Cell的數(shù)量來(lái)減少數(shù)據(jù)的重復(fù)計(jì)算.進(jìn)而來(lái)代替所有的鄰居Cell，每個(gè)Reducer只考慮Cell的id等于主Cell格子的id，如圖1所示：只考慮深色(綠色)與淺色的Cell).其余的Reducer計(jì)算鄰居Cell中點(diǎn)與點(diǎn)的距離(C01和C10).但這種方法仍然會(huì)計(jì)算不必要的計(jì)算,例如每個(gè)點(diǎn)只與以該點(diǎn)為中心，以2ε為邊長(zhǎng)的正方形有join結(jié)果，其他點(diǎn)的計(jì)算是多余的.

Fig. 1 The grid division.圖1 等網(wǎng)格區(qū)域劃分

可見(jiàn)MRDSJ算法由于存在大量的不必要的計(jì)算而降低了它的有效性.在本文中，我們通過(guò)采用有效的基于坐標(biāo)過(guò)濾技術(shù)來(lái)解決這種問(wèn)題，同時(shí)通過(guò)內(nèi)切圓的方法也可以處理聚集的數(shù)據(jù)，提高了算法的效率.

2 基于MapReduce的坐標(biāo)過(guò)濾和降維技術(shù)

2.1 基于MapReduce的坐標(biāo)過(guò)濾技術(shù)

Fig. 2 Reducing the replication calculate.圖2 減少重復(fù)計(jì)算

主要思想是利用滑動(dòng)窗口的想法，以待處理數(shù)據(jù)點(diǎn)為中心，以2ε為邊長(zhǎng)的正方形形成一個(gè)滑動(dòng)窗口，join結(jié)果在這個(gè)滑動(dòng)窗口產(chǎn)生，其他點(diǎn)的計(jì)算是多余的.基于文獻(xiàn)[4]的數(shù)據(jù)劃分的方式，分割成等寬網(wǎng)格的區(qū)域Cell.每個(gè)Cell中分布著不同的點(diǎn).主Cell與鄰Cell間做相似自連接操作，僅計(jì)算id比主Cell的id小的相鄰Cell的join操作[4].坐標(biāo)過(guò)濾技術(shù)采取同時(shí)利用2點(diǎn)的同一維坐標(biāo)間的距離差與約束ε進(jìn)行比較，凡是任一維度的坐標(biāo)差大于約束ε值時(shí)，都不再做進(jìn)一步的join計(jì)算.因此減少了候選集對(duì)象的數(shù)量，如圖2所示虛線框(紅色)是滑動(dòng)窗口，所有滑動(dòng)窗口外的點(diǎn)都不需要與該點(diǎn)進(jìn)行join計(jì)算.如果小于約束ε，則將這2點(diǎn)列入候選集中.

R與R的相似自連接操作定義的表達(dá)式見(jiàn)式(2)：

R??εR={(idp,idq)∈R×R|d(datap,

dataq)≤ε}.

(2)

輸出結(jié)果是集合笛卡兒積的子集，為outdsj∈R×R.idp代表點(diǎn)p所在的Cell的id，datap代表點(diǎn)p的坐標(biāo)，d(datap,dataq)表示歐幾里得距離.

例1. 假設(shè)圖2中的C11中的點(diǎn)p坐標(biāo)(3,3)，C01中的點(diǎn)q坐標(biāo)為(2,2.5)約束ε=2.因?yàn)镃11和C01在同一個(gè)Y維度上，不在同一個(gè)X維度上，所以只計(jì)算X的坐標(biāo)差3-2=1<2，即選入候選集.C00中的點(diǎn)坐標(biāo)為(1.4,1.4)，與點(diǎn)C11中p計(jì)算時(shí)，X，Y都不在同一個(gè)維度.因此都計(jì)算2-1.4=0.6, 3.5-1.4=2.1>2，不選入候選集中.

列入候選集后，再進(jìn)行自連接操作.距離小于閾值的則列入結(jié)果集中，得到最終相似對(duì).該方法起到了多重過(guò)濾的效果，提高了算法的運(yùn)行效率，同時(shí)也避免了不必要的計(jì)算.

算法1. 基于坐標(biāo)過(guò)濾技術(shù).

首次操作，讀取INPUT下的所有生成的數(shù)據(jù)點(diǎn)集，其中包括各個(gè)點(diǎn)的原始坐標(biāo).為了使數(shù)據(jù)結(jié)構(gòu)更加清晰明確，輸入的點(diǎn)文件格式為JSON格式，從速度性能維度上考慮，數(shù)據(jù)結(jié)構(gòu)化工具采用業(yè)內(nèi)領(lǐng)先的阿里巴巴的開(kāi)源工程Fast-Json.

輸入：輸入文件目錄INPUT，占硬盤(pán)大小為600 MB，文件數(shù)30個(gè)，文件內(nèi)容皆為JSON格式的數(shù)據(jù)點(diǎn)信息；

輸出：輸出文件目錄OUTPUT，包含所有相似對(duì)，其文件數(shù)為生成的點(diǎn)所占用的Cell的歸檔數(shù)據(jù)數(shù).

mapjob:

①map(LongWritablekey, Textvalue)；

② Pointp=parse(json)；*將文件的數(shù)據(jù)反序列化成點(diǎn)p*

③ Cellc=getcellbyPoint(p)；*將點(diǎn)坐標(biāo)轉(zhuǎn)換成Cell坐標(biāo)，2套坐標(biāo)系并行處理*

④ 利用算法2根據(jù)該cell生成周?chē)?個(gè)需要compare的cell集合;

⑤ for (cell:cellList)

⑥write(cell,key);

⑦ endfor

⑧ 利用算法3類(lèi)似倒排索引，以各個(gè)集合為key,該點(diǎn)為value寫(xiě)入到reduce函數(shù).

reducejob:

①reduce(Cellc, Iterable〈Point〉points)

② 通過(guò)map傳遞過(guò)來(lái)的遍歷器去獲取點(diǎn)并劃分出主Cell和鄰Cell這2個(gè)集合;

③pmainList=cell.getPoints();

④ for (i:size)

⑤potherList=cell.getOther() ;

⑥ 通過(guò)核心算法LessThanE去判別2個(gè)點(diǎn)是否距離小于ε;

⑦result.addAll(p1,p2);

⑧ endfor

⑨ boolb=LessThanE(p1,p2);

⑩writer.write(cell).*最后通過(guò)不同的Cell歸檔到不同的結(jié)果文件中*

結(jié)合整體流程，我們可以知道本算法主要是利用網(wǎng)格區(qū)域的劃分、坐標(biāo)的過(guò)濾計(jì)算及聚集區(qū)域的內(nèi)切圓方法來(lái)實(shí)現(xiàn)相似自連接操作.

顯然算法1的map步的計(jì)算復(fù)雜性為O(n)，其中n為map的輸入;reduce步的計(jì)算復(fù)雜性為O(n×m)，其中n為reduce的主cell的輸入大小，m為reduce的環(huán)繞式Cell輸入大小加上主Cell的輸入大小.

算法2.GenerateAroundcell.

完成網(wǎng)格劃分和生成點(diǎn)坐標(biāo)的二次生成坐標(biāo)系即為Cell坐標(biāo)系.通過(guò)點(diǎn)p的Cellp所在主Cell坐標(biāo)系位置compare并generate方法生成鄰近的Othercell.MaxX代表點(diǎn)坐標(biāo)系最大X，而unit代表點(diǎn)坐標(biāo)系轉(zhuǎn)換Cell坐標(biāo)系的單位，通過(guò)與這2個(gè)對(duì)比生成需要的圍繞式的左側(cè)Cell以及右側(cè)Cell;然后根據(jù)步驟①生成的點(diǎn)數(shù)去判斷是否存在左下Cell;最后分析Cell分布情況 .主Cell的左上也應(yīng)該納入對(duì)比GenerateAroundCell函數(shù)的偽代碼如下：

①otherlist=gerateCell(p.x,p.unit);

②list.add(Cell′(p.x-1,p.y));

③list.add(Cell′l(p.x,p.y-1));

④ ifotherlist.size==2

⑤lowerleft=geratelowerleft(p.x,p.unit);

⑥ return;

⑦ endif

⑧l(xiāng)ist.add=Cell′(p.x-1,p.y-1);

⑨upperleft=gerateupperleft(p.x,p.unit)；

⑩ returnCell′(p.x-1,p.y+1).

通過(guò)以上算法生成了環(huán)繞式Cell分布集list用作對(duì)比主Cell.

將海量數(shù)據(jù)劃分區(qū)域，確定Cell周邊5個(gè)必算(C11和C11,C11和C10,C11和C01,C11和C00,C10和C01的計(jì)算)鄰Cell后.利用算法3針對(duì)每個(gè)Cell采用坐標(biāo)過(guò)濾技術(shù)進(jìn)一步剪枝，盡可能少地選定候選集的數(shù)目.

容易看出算法2的計(jì)算復(fù)雜性為O(1).

算法3.lessThanE算法.

由于點(diǎn)的數(shù)據(jù)集隨機(jī)分布的特點(diǎn)，對(duì)比數(shù)據(jù)可能出現(xiàn)2個(gè)點(diǎn)位于同一坐標(biāo)的問(wèn)題，在此視作同一個(gè)點(diǎn)不作對(duì)比.當(dāng)主Cell與環(huán)繞Cell對(duì)比時(shí)，根據(jù)三角不等式，不在同一維度的，優(yōu)先對(duì)比2點(diǎn)維度的坐標(biāo)差的絕對(duì)值；再與ε做compare，若大于直接過(guò)濾掉.當(dāng)前2步過(guò)濾出大部分集合后,繼續(xù)做自連接操作后的結(jié)果與ε作比較，小于的則納入result集中.lessThanE函數(shù)的偽分布代碼如下：

① ifcompare(p1.x,p2.x) &&compare(p1.y,p2.y)

② return false；

③ endif

④ if abs(p1.x-p2.x)>ε‖abs(p1.y-p2.y)>ε

⑤ return false；

⑥ endif

⑦ ifpythagorean(p1,p2)<ε

⑨ endif

⑩pythagorean(p1,p2)；

通過(guò)以上lessThanE算法即可得出相鄰的Cell的符合預(yù)期點(diǎn)集合.容易看出算法3的計(jì)算復(fù)雜性為O(1).

2.2 高維降維方法

對(duì)于高維數(shù)據(jù)，采用了我們提出的新降維技術(shù)將高維數(shù)據(jù)降為2維數(shù)據(jù)，并且保證相似自連接結(jié)果保持在新數(shù)據(jù)中.我們有下面一個(gè)定理.

證畢.

3 聚集區(qū)域內(nèi)切圓算法

3.1 正方形區(qū)域劃分中的內(nèi)切圓算法

主要針對(duì)主Cell中的點(diǎn)和主Cell中的點(diǎn)之間的自連接操作.為了檢測(cè)算法可以克服存在聚集數(shù)據(jù)的特殊情況，我們生成了正態(tài)分布的點(diǎn)集合，根據(jù)聚類(lèi)方法找到中心點(diǎn)，以中心點(diǎn)為圓心并以ε2為半徑畫(huà)圓.根據(jù)三角形定理，圓內(nèi)所有點(diǎn)之間的距離都會(huì)小于ε，利用算法4進(jìn)行過(guò)濾減枝.如圖3所示，利用三角不等式原理：ε2+ε2=ε.因此不必進(jìn)行圓內(nèi)的任意2點(diǎn)之間的距離運(yùn)算，只計(jì)算圓外的點(diǎn)之間的距離、圓內(nèi)點(diǎn)和圓外的點(diǎn)之間的距離.圓內(nèi)的任意2點(diǎn)之間組成的結(jié)果對(duì)都在結(jié)果集中.

Fig. 3 Dividing gather area.圖3 聚集區(qū)域劃分

定義1. 聚集數(shù)據(jù)點(diǎn).一個(gè)Cell被稱(chēng)為是聚集點(diǎn)，即Cell中所包含的數(shù)據(jù)點(diǎn)較多，即數(shù)據(jù)點(diǎn)個(gè)數(shù)n較大，例如n>10.

由于數(shù)據(jù)屬于聚集型數(shù)據(jù)，每個(gè)Cell中符合小于ε的點(diǎn)會(huì)更加密集，所以單個(gè)Cell的優(yōu)化更為必要.以Cell邊長(zhǎng)ε為最大直徑的內(nèi)切圓，圓內(nèi)散布的任何一對(duì)點(diǎn)都可以視作距離小于ε.首先取到主Cell的點(diǎn)集,在Cell中尋找聚類(lèi)中心點(diǎn).通過(guò)compare算法遍歷點(diǎn)集與中心點(diǎn)比較,符合條件的加入result集合.將mainlist的點(diǎn)與result點(diǎn)集進(jìn)行隔離，mainlist剩余的點(diǎn)互相比較生成結(jié)果集合，最后主Cell結(jié)果集為result.

算法4. 內(nèi)切圓算法.

輸入：聚集分布的數(shù)據(jù)集；

輸出：result1；*相似的結(jié)果對(duì)*

result2.*內(nèi)切圓中的點(diǎn)*

①mainlist=cellpoint(c);

②point=cell.center();

③ for (i:mainlist)

④ ifcompare(i,point)<ε2

⑤result2.add(i)；

⑥ endif

⑦ endfor

⑧mainlist.remove(result2)；

⑨ for (i:mainlist)

⑩ for (j:mainlist)

易計(jì)算得到內(nèi)切圓算法的計(jì)算復(fù)雜性為O(n)+O(m×n+m×m)，其中n為輸入的點(diǎn)數(shù)，m為Cell中內(nèi)切圓外的點(diǎn)數(shù).

3.2 正六邊形區(qū)域劃分中的內(nèi)切圓算法

Fig. 4 Hexagonal area region.圖4 正六邊形區(qū)域劃分

Fig. 5 Hexagon inscribed circle.圖5 正六邊形內(nèi)切圓

為了證明正六邊形的區(qū)域劃分方法對(duì)于內(nèi)切圓算法是最優(yōu)的，我們需要先給出單一形狀圖形覆蓋全平面的概念.單一形狀覆蓋全平面，是指以大小確定的單一形狀圖形通過(guò)拼接可以無(wú)限延伸，并且沒(méi)有空隙的填滿整個(gè)全平面，換句話說(shuō)只有大小相等的一種圖形存在,它可以是正多邊形，也可以是非正多邊形，例如菱形、平行四邊形等.

定理2. 在所有單一形狀圖形覆蓋平面的正n邊形劃分中正六邊形是邊數(shù)最多的.

證明. 正n邊形的外角和為2π,我們有外角一定是2πn，所以?xún)?nèi)角就是π-2πn.由于單一形狀圖形覆蓋平面所以知道都是由同一個(gè)形狀圖形拼接起來(lái)的，所以每個(gè)頂點(diǎn)一定是由幾個(gè)正多邊形構(gòu)成，即頂點(diǎn)應(yīng)該滿足：

其中,k為自然數(shù).當(dāng)n=6時(shí)，k=3.當(dāng)n>6時(shí)，k=2n(n-2)，上面的方程對(duì)于自然數(shù)集合無(wú)解，所以正六邊形是所有單一形狀圖形覆蓋平面的正n邊形劃分中邊數(shù)最多的.

證畢.

對(duì)于內(nèi)切圓算法，正n邊形劃分的算法效率隨n的增加而提高,但是由定理2可知，正六邊形區(qū)域劃分是正n邊形區(qū)域劃分中最優(yōu)的劃分.

4 實(shí) 驗(yàn)

本節(jié)我們對(duì)所提出的新算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并與基準(zhǔn)方案：基于距離的相似自連接(MRDSJ)進(jìn)行性能對(duì)比，MRDSJ采用的基本算法是基于文獻(xiàn)[4]提出的一種基于MapReduce框架的算法.我們同時(shí)測(cè)試了2種算法在并行環(huán)境下的性能對(duì)比，主要利用合成數(shù)據(jù)來(lái)測(cè)試不同數(shù)據(jù)集大小對(duì)執(zhí)行時(shí)間的影響、不同節(jié)點(diǎn)數(shù)對(duì)執(zhí)行時(shí)間的影響及聚集點(diǎn)在正方形劃分和正六邊形劃分時(shí)內(nèi)切圓算法的性能分析.真實(shí)生物數(shù)據(jù)下不同節(jié)點(diǎn)數(shù)對(duì)執(zhí)行時(shí)間的影響.

1) 合成數(shù)據(jù)——隨機(jī)產(chǎn)生的向量坐標(biāo)，數(shù)據(jù)量為500萬(wàn)、1000萬(wàn)、2000萬(wàn).坐落在100萬(wàn)個(gè)格子中，每個(gè)格子10×10，ε=10.用C++編寫(xiě)了正態(tài)分布產(chǎn)生函數(shù)生成的合成聚集數(shù)據(jù)為10萬(wàn)、20萬(wàn)、30萬(wàn)個(gè)點(diǎn).

2) 真實(shí)數(shù)據(jù)——采用數(shù)據(jù)量為200萬(wàn)的DNA序列的生物數(shù)據(jù)，數(shù)據(jù)來(lái)源于1000 Genome國(guó)際項(xiàng)目Sequencing數(shù)據(jù)[16].

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)是在Mac上實(shí)現(xiàn)，硬件環(huán)境由8臺(tái)普通的PC機(jī)組成的一個(gè)集群，1臺(tái)為Namenode的機(jī)器作為Master，7臺(tái)為Datanode的機(jī)器.節(jié)點(diǎn)配置如下：CPU為Q9650 3.00 GHz，Memory為8 GB，Disk為500 GB OS64b Ubuntu12.03 sever.

4.2 實(shí)驗(yàn)結(jié)果及分析

4.2.1 數(shù)據(jù)量影響計(jì)算距離和執(zhí)行時(shí)間

圖6和圖7是在節(jié)點(diǎn)數(shù)為4時(shí)3種算法在不同的數(shù)據(jù)集上的距離計(jì)算量和執(zhí)行時(shí)間的結(jié)果.從實(shí)驗(yàn)數(shù)據(jù)上可以看出，距離計(jì)算量和執(zhí)行時(shí)間都隨著數(shù)據(jù)集的增大而增加.圖6顯示MRDSJ和PHIDJ算法的距離計(jì)算量要比坐標(biāo)過(guò)濾算法距離計(jì)算的數(shù)量大，原因是坐標(biāo)過(guò)濾算法使用了多種過(guò)濾技術(shù)如滑動(dòng)窗口過(guò)濾和坐標(biāo)過(guò)濾，剪枝掉了一部分不是結(jié)果集的向量對(duì)的距離計(jì)算.而MRDSJ和PHIDJ僅是網(wǎng)格劃分時(shí)進(jìn)行了少量的剪枝，所以正如實(shí)驗(yàn)結(jié)果所顯示，坐標(biāo)過(guò)濾算法產(chǎn)生的距離計(jì)算量少.圖7顯示了在節(jié)點(diǎn)數(shù)為4時(shí)，不同數(shù)據(jù)集的大小對(duì)執(zhí)行時(shí)間的影響.當(dāng)數(shù)據(jù)集為500萬(wàn)時(shí)，新算法用的時(shí)間為460 s，而MRDSJ算法的運(yùn)行時(shí)間為680 s，PHIDJ算法的運(yùn)行時(shí)間為570 s.本文是采用基于坐標(biāo)過(guò)濾的方法，在已有算法的基礎(chǔ)上進(jìn)行優(yōu)化，使得運(yùn)行的效率提高.另外，隨著數(shù)據(jù)集的增大，2種算法的運(yùn)行時(shí)間呈增長(zhǎng)趨勢(shì),并且數(shù)據(jù)集越大，新算法的效率提高的越多，越節(jié)省時(shí)間.

Fig. 6 Impact of different data set size on the distance calculate.圖6 數(shù)據(jù)集大小對(duì)距離計(jì)算量的影響

Fig. 7 Impact of different data set size on the execution time.圖7 數(shù)據(jù)集大小對(duì)執(zhí)行時(shí)間的影響

4.2.2 不同的計(jì)算代價(jià)對(duì)性能的影響

坐標(biāo)過(guò)濾算法整體的計(jì)算過(guò)程可以分成3個(gè)階段：數(shù)據(jù)加載階段(Cd-Load)、滑動(dòng)窗口過(guò)濾階段(Cd-Slide)和坐標(biāo)過(guò)濾階段(Cd-Filter).同時(shí)實(shí)驗(yàn)對(duì)比的MRDSJ算法也分為3個(gè)階段：數(shù)據(jù)加載階段(Md-Load)、點(diǎn)與Cell邊界值過(guò)濾(Md-Cells)和點(diǎn)對(duì)之間過(guò)濾(Md-Pairs).實(shí)驗(yàn)結(jié)果如圖8所示通過(guò)不同數(shù)據(jù)集合的大小，分別對(duì)比2種算法在不同計(jì)算環(huán)節(jié)上對(duì)算法時(shí)間的影響.可見(jiàn)數(shù)據(jù)加載階段，2種算法基本相同,因?yàn)槎际亲x取數(shù)據(jù)并進(jìn)行劃分；在滑動(dòng)窗口過(guò)濾階段坐標(biāo)過(guò)濾階段的執(zhí)行時(shí)間比MRDSJ的Cell過(guò)濾和點(diǎn)對(duì)過(guò)濾階段所用的時(shí)間短，主要原因是滑動(dòng)窗口過(guò)濾有效地剪枝了周邊3個(gè)Cell，而Cell邊界過(guò)濾僅剪枝1個(gè)Cell，并且坐標(biāo)過(guò)濾僅計(jì)算X或Y維上坐標(biāo)的差值來(lái)過(guò)濾，而MRDSJ算法點(diǎn)對(duì)過(guò)濾是通過(guò)計(jì)算距離來(lái)實(shí)現(xiàn)過(guò)濾.可見(jiàn)通過(guò)對(duì)計(jì)算代價(jià)的分解，可以明顯看到坐標(biāo)過(guò)濾算法性能上的提高.

Fig. 8 Impact of different computation cost on performance.圖8 不同的計(jì)算代價(jià)對(duì)性能的影響

4.2.3 不同節(jié)點(diǎn)數(shù)對(duì)執(zhí)行時(shí)間的影響

圖9(a)展示了針對(duì)500萬(wàn)數(shù)據(jù)集，不同節(jié)點(diǎn)數(shù)對(duì)執(zhí)行時(shí)間的影響.在執(zhí)行MR-DSJ時(shí)，1個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間1 440 s，PHIDJ算法的運(yùn)行時(shí)間為1 380 s.本文基于坐標(biāo)過(guò)濾技術(shù)的算法，運(yùn)行時(shí)間是1 260 s.說(shuō)明在偽分布式環(huán)境下，該算法仍然可以提高執(zhí)行速度.當(dāng)節(jié)點(diǎn)數(shù)為4時(shí)，利用MapReduce強(qiáng)大的并行處理能力，該算法執(zhí)行時(shí)間明顯比原有算法少，更加說(shuō)明該算法的過(guò)濾效果明顯，減少了通訊代價(jià)及成本.

圖9(b)則展示了針對(duì)1 000萬(wàn)數(shù)據(jù)集的變化情況.8個(gè)節(jié)點(diǎn)時(shí)MRDSJ算法用了620 s，PHIDJ算法的運(yùn)行時(shí)間為580 s，而基于坐標(biāo)過(guò)濾算法用440 s.8個(gè)節(jié)點(diǎn)時(shí)，由于串行時(shí)間的存在，因此并行的執(zhí)行時(shí)間不會(huì)由于節(jié)點(diǎn)的增多而減少得過(guò)少，會(huì)有一個(gè)下限.但是相比較于更少的節(jié)點(diǎn)來(lái)說(shuō)，執(zhí)行時(shí)間還是很短，充分體現(xiàn)了其并行性.

Fig. 9 Impact of different nodes on the execution time.圖9 不同節(jié)點(diǎn)數(shù)下執(zhí)行時(shí)間的對(duì)比

從圖9(a)(b)對(duì)比還可以看出，數(shù)據(jù)集越大，雖然執(zhí)行的時(shí)間越長(zhǎng)，但是隨著數(shù)據(jù)集的增加，算法速度要比數(shù)據(jù)集少得快，并且節(jié)點(diǎn)數(shù)越多，效率提高越明顯，可能是存在數(shù)據(jù)高速緩存的原因.我們的算法比原算法的速度更快.

4.2.4 基于聚集區(qū)域的Cell性能分析

Fig. 10 Impact of different data set size on the execution time.圖10 不同數(shù)據(jù)集大小對(duì)執(zhí)行時(shí)間的影響

根據(jù)正態(tài)分布產(chǎn)生函數(shù)生成合成數(shù)據(jù)為10萬(wàn)、20萬(wàn)、30萬(wàn)個(gè)密集點(diǎn)，分布在主Cell中.正方形的內(nèi)切圓算法利用內(nèi)切圓算法把區(qū)域劃分為圓內(nèi)A部分和圓外B部分.省去B部分的計(jì)算，只有A部分及AB部分的運(yùn)算，因此可以達(dá)到如圖10所示的結(jié)果.在單個(gè)Cell中利用正方形內(nèi)切圓算法(Square-ic)，隨著數(shù)據(jù)量的增加，運(yùn)行時(shí)間也隨著增加.但是我們的新算法要比原有算法節(jié)省時(shí)間，而且數(shù)據(jù)量越大，算法提高的效率越明顯.與原有MRDSJ算法相比較，平均提高了60%以上.而采用六邊形區(qū)域劃分(Hexagonal-ic)的方式，進(jìn)一步較少了候選集計(jì)算的數(shù)量，使得內(nèi)切圓算法比原有MRDSJ算法平均提高了80%以上.

本文采用的是散列存儲(chǔ)(Hash storage)結(jié)構(gòu)，為了更全面地對(duì)性能進(jìn)行分析，分別對(duì)不同的數(shù)據(jù)存儲(chǔ)方式通過(guò)控制變量來(lái)驗(yàn)證不同的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)對(duì)性能的影響，通過(guò)驗(yàn)證線性存儲(chǔ)(liner storage)、隨機(jī)存儲(chǔ)(random storage)以及樹(shù)狀存儲(chǔ)(B+tree)的不同存儲(chǔ)結(jié)構(gòu)對(duì)整體性能的影響，得出實(shí)驗(yàn)結(jié)果如圖11所示.可見(jiàn)，不同的存儲(chǔ)結(jié)構(gòu)之間的差異不大，對(duì)性能的影響不大.

Fig. 11 Impact of different storage structure on performance.圖11 不同存儲(chǔ)結(jié)構(gòu)對(duì)性能影響

4.2.5 真實(shí)數(shù)據(jù)的性能分析

本文采用200萬(wàn)的生物DNA序列，將堿基序列轉(zhuǎn)化成二進(jìn)制數(shù)，每20個(gè)堿基字符串為一組，利用滑動(dòng)窗口得到200萬(wàn)組字符串，進(jìn)行相似自連接操作獲得相近的堿基序列.設(shè)A=00，T=01，G=10，U=11，一組字符串平均劃分前后2個(gè)部分作為坐標(biāo)參數(shù).相似度設(shè)為ε=2，比較不同節(jié)點(diǎn)下的運(yùn)行時(shí)間.如圖12可以看出同，隨著節(jié)點(diǎn)數(shù)的增加，運(yùn)行的時(shí)間隨之減少，但是我們的算法要比MRDSJ算法快.

Fig. 12 Impact of different nodes of real data on the execution time.圖12 真實(shí)數(shù)據(jù)的不同節(jié)點(diǎn)數(shù)對(duì)執(zhí)行時(shí)間的影響

5 結(jié)束語(yǔ)

目前有很多關(guān)于相似性連接操作的算法，但是基于距離相似自連接操作的高效算法并不多見(jiàn).本文在網(wǎng)格劃分的基礎(chǔ)上使用基于坐標(biāo)過(guò)濾的算法，減少了候選集的數(shù)量及不必要的距離計(jì)算.同時(shí)針對(duì)聚集的點(diǎn)，采用內(nèi)切圓的算法進(jìn)一步過(guò)濾，當(dāng)采用六邊形區(qū)域劃分時(shí)，內(nèi)切圓的算法效率提高80%以上.未來(lái)將研究聚集區(qū)域結(jié)合高效的聚類(lèi)算法發(fā)現(xiàn)聚集點(diǎn)，并深入研究最優(yōu)區(qū)域劃分方法.

[1]Chaudhuri S, Ganti V, Kaushik R. A primitive operator for similarity joins in data cleaning[C] //Proc of the 22nd IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2006: 5

[2]Wang G, University N. Efficient similarity joins for near duplicate detection[J]. ACM Trans on Data Base Systems, 2008, 36(3): 563-574

[3]Baraglia R, Morales G D F, Lucchese C. Document similarity self-join with MapReduce[C] //Proc of the 10th IEEE ICDM’10. Piscataway, NJ: IEEE, 2010:731-736

[4]Seidl T, Fries S, Boden B. Distance-based self-join for large-scale vector data analysis with MapReduce[C] //Proc of the 15th BTW Conf on Database Systems for Business, Technology, and Web. Magdeburg, Germany: BTW, 2013: 37-56

[5]Pang Jun, Gu Yu, Xu Jia, et al. Research progress of similarity join query [J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(1): 1-13 (in Chinese)(龐俊, 谷峪, 許嘉, 等.相似性連接查詢(xún)技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)科學(xué)與探索, 2013, 7(1): 1-13)

[6]Ma Youzhong, Ci Xiang, Meng Xiaofeng. Parallel Top-kjoin on massive high-dimensional vectors[J]. Chinese Journal of Computers, 2015, 38(1): 86-98 (in Chinese)(馬友忠, 慈祥, 孟小峰. 海量高維向量的并行Top-k連接查詢(xún)[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(1): 86-98)

[7]Lu Wei , Shen Yanyan, Chen Su, et al. Efficient processing ofknearest neighbor joins using MapReduce[J]. Proceedings of the VLDB Endowment, 2012, 5(10): 1016-1027

[8]Zhang Chi, Li Feifei, Jestes J. Efficient parallelkNN joins for large data in MapReduce[C] //Proc of the 15th Int Conf on Extending Database Technology. New York: ACM, 2012: 38-49

[9]Silva Y N, Reed J M, Tsosie L M. MapReduce-based similarity join for metric spaces[C/OL] //Proc of the 1st Int Workshop on Cloud Intelligence. New York: ACM, 2012: 1-8 [2015-08-25]. http://dl.acm.org/citation.cfm?doid=2347673.2347676

[10]Blanas S, Patel J M, Ercegovac V, et al. A comparison of join algorithms for log processing in MapReduce[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 975-986

[11]Afrati F N, Ullman J D. Optimizing multiway joins in a MapReduce environment[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(9): 1282-1298

[12]Wang Wei, Qin Jianbin, Xiao Chuan, et al. VChunkJoin: An efficient algorithm for edit similarity joins[J]. IEEE Trans on Knowledge and Data Engineering, 2013, 25(8): 1916-1929

[13]Song Ge, Rochas J, Huet F, et al. Solutions for processingknearest neighbor joins for massive data on MapReduce[C] //Proc of the 23rd Int Conf on Parallel, Distributed and Network-Based Processing. Piscataway, NJ: IEEE, 2015: 279-287

[14]Li Tiantian, Yu Ge, Guo Chaopeng, et al. Multi-way join optimization approachbased on MapReduce[J]. Journal of Computer Research and Development, 2016, 53(2): 467-478 (in Chinese)(李甜甜, 于戈, 郭朝鵬, 等. 基于MapReduce的多元連接優(yōu)化方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(2): 467-478)

[15]Fries S, Boden B, Stepien G, et al. PHIDJ: Parallel similarity self-join for high-dimensional vector data with MapReduce[C] //Proc of the 30th Int Conf on Data Engineering .Piscataway, NJ: IEEE, 2014: 796-807

[16]Abecasis G R, Adam A, Brooks L D, et al. An integrated map of genetic variation from 1,092 human genomes.[J]. Nature, 2012, 491(7422): 56-65Bao Guanghui, born in 1991. Master candidate. Her main research interests include analysis and mining on massive data.

Zhang Zhaogong, born in 1963. Professor and MSc supervisor. His main research interests include massive data mining and bioinformatics, etc.

Li Jianzhong, born in 1950. Professor and PhD supervisor. His main research interests include massive data management and computing, wireless sensor network, ect.

Xuan Ping, born in 1979. PhD and associate professor. Her main research interests includes massive data mining and bioinformatics.

Novel MapReduce-Based Similarity Self-Join Method: Filter and In-Circle Algorithm

Bao Guanghui1, Zhang Zhaogong1, Li Jianzhong1,2, and Xuan Ping1

1(School of Computer Science and Technology, Heilongjiang University, Harbin 150080)2(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

Similarity self-join is a very important study in many applications. For the massive data sets, MapReduce can provide an effective distributed computing framework, in particular, similarity self-join can be applied on the framework. There are still problems, such as fine partition method, are applied to cluster data area for load balancing, but it is not easy to implement. Existing algorithms can’t effectively accomplish similarity self-join operations for the massive data sets. In this paper, we propose two novel algorithms of similarity self-join on the MapReduce framework, and use coordinate-filtering techniques to get the valid candidate sets and use the in-circle method on the hexagon-based partition area. Those coordinate-filtering techniques are based on equal-width grid partition, and adopt the restriction that two points have more distances than two projective points in the same axis, and can drop obviously some candidate set. We also proof that the hexagon-based partition is the best form in all normal partition. Our experimental results demonstrate that the novel method has an advantage over the other join algorithms for cluster data area which improves efficiency over 80%. The algorithm can effectively solve the problem of the similarity self-join for the massive data in cluster data area.

massive data sets; filter; similarity self-join; data partition; Hadoop platform; MapReduce programming model

2015-09-01；

2016-05-03

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB316200)；國(guó)家自然科學(xué)基金項(xiàng)目(61302139) This work was supported by the National Basic Research Program of China (973 Program) (2012CB316200) and the National Natural Science Foundation of China (61302139).

張兆功(zhaogong.zhang@qq.com)

TP311.13