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

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

?

基于MapReduce的相似自連接新方法：過濾和內切圓算法

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

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

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

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

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

關于集合R，S的θ-join的定義為

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

(1)

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

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

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

本文的主要貢獻有3點:

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

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

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

1 相關工作

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

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

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

1.1 MapReduce框架下的MR-DSJ算法

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

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

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

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

2 基于MapReduce的坐標過濾和降維技術

2.1 基于MapReduce的坐標過濾技術

Fig. 2 Reducing the replication calculate.圖2 減少重復計算

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

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

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

dataq)≤ε}.

(2)

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

例1. 假設圖2中的C11中的點p坐標(3,3)，C01中的點q坐標為(2,2.5)約束ε=2.因為C11和C01在同一個Y維度上，不在同一個X維度上，所以只計算X的坐標差3-2=1<2，即選入候選集.C00中的點坐標為(1.4,1.4)，與點C11中p計算時，X，Y都不在同一個維度.因此都計算2-1.4=0.6, 3.5-1.4=2.1>2，不選入候選集中.

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

算法1. 基于坐標過濾技術.

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

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

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

mapjob:

①map(LongWritablekey, Textvalue)；

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

③ Cellc=getcellbyPoint(p)；*將點坐標轉換成Cell坐標，2套坐標系并行處理*

④ 利用算法2根據(jù)該cell生成周圍5個需要compare的cell集合;

⑤ for (cell:cellList)

⑥write(cell,key);

⑦ endfor

⑧ 利用算法3類似倒排索引，以各個集合為key,該點為value寫入到reduce函數(shù).

reducejob:

①reduce(Cellc, Iterable〈Point〉points)

② 通過map傳遞過來的遍歷器去獲取點并劃分出主Cell和鄰Cell這2個集合;

③pmainList=cell.getPoints();

④ for (i:size)

⑤potherList=cell.getOther() ;

⑥ 通過核心算法LessThanE去判別2個點是否距離小于ε;

⑦result.addAll(p1,p2);

⑧ endfor

⑨ boolb=LessThanE(p1,p2);

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

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

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

算法2.GenerateAroundcell.

完成網(wǎng)格劃分和生成點坐標的二次生成坐標系即為Cell坐標系.通過點p的Cellp所在主Cell坐標系位置compare并generate方法生成鄰近的Othercell.MaxX代表點坐標系最大X，而unit代表點坐標系轉換Cell坐標系的單位，通過與這2個對比生成需要的圍繞式的左側Cell以及右側Cell;然后根據(jù)步驟①生成的點數(shù)去判斷是否存在左下Cell;最后分析Cell分布情況 .主Cell的左上也應該納入對比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).

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

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

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

算法3.lessThanE算法.

由于點的數(shù)據(jù)集隨機分布的特點，對比數(shù)據(jù)可能出現(xiàn)2個點位于同一坐標的問題，在此視作同一個點不作對比.當主Cell與環(huán)繞Cell對比時，根據(jù)三角不等式，不在同一維度的，優(yōu)先對比2點維度的坐標差的絕對值；再與ε做compare，若大于直接過濾掉.當前2步過濾出大部分集合后,繼續(xù)做自連接操作后的結果與ε作比較，小于的則納入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)；

通過以上lessThanE算法即可得出相鄰的Cell的符合預期點集合.容易看出算法3的計算復雜性為O(1).

2.2 高維降維方法

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

證畢.

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

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

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

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

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

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

算法4. 內切圓算法.

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

輸出：result1；*相似的結果對*

result2.*內切圓中的點*

①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)

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

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

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

Fig. 5 Hexagon inscribed circle.圖5 正六邊形內切圓

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

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

證明. 正n邊形的外角和為2π,我們有外角一定是2πn，所以內角就是π-2πn.由于單一形狀圖形覆蓋平面所以知道都是由同一個形狀圖形拼接起來的，所以每個頂點一定是由幾個正多邊形構成，即頂點應該滿足：

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

證畢.

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

4 實 驗

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

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

2) 真實數(shù)據(jù)——采用數(shù)據(jù)量為200萬的DNA序列的生物數(shù)據(jù)，數(shù)據(jù)來源于1000 Genome國際項目Sequencing數(shù)據(jù)[16].

4.1 實驗環(huán)境

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

4.2 實驗結果及分析

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

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

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

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

4.2.2 不同的計算代價對性能的影響

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

Fig. 8 Impact of different computation cost on performance.圖8 不同的計算代價對性能的影響

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

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

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

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

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

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

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

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

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

Fig. 11 Impact of different storage structure on performance.圖11 不同存儲結構對性能影響

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

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

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

5 結束語

目前有很多關于相似性連接操作的算法，但是基于距離相似自連接操作的高效算法并不多見.本文在網(wǎng)格劃分的基礎上使用基于坐標過濾的算法，減少了候選集的數(shù)量及不必要的距離計算.同時針對聚集的點，采用內切圓的算法進一步過濾，當采用六邊形區(qū)域劃分時，內切圓的算法效率提高80%以上.未來將研究聚集區(qū)域結合高效的聚類算法發(fā)現(xià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)(龐俊, 谷峪, 許嘉, 等.相似性連接查詢技術研究進展[J]. 計算機科學與探索, 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連接查詢[J]. 計算機學報, 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]. 計算機研究與發(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

國家“九七三”重點基礎研究發(fā)展計劃基金項目(2012CB316200)；國家自然科學基金項目(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