鄧詩卓，信俊昌，聶鐵錚，王國仁

東北大學 計算機科學與工程學院，沈陽 110819

雙綴過濾的大數(shù)據(jù)相似性連接處理算法*

鄧詩卓，信俊昌，聶鐵錚，王國仁+

東北大學 計算機科學與工程學院，沈陽 110819

相似性連接；權(quán)重相似性連接；大數(shù)據(jù)；過濾；Spark

1 引言

隨著信息技術(shù)的飛速發(fā)展，各行各業(yè)的數(shù)據(jù)都逐漸信息化，數(shù)據(jù)的存儲形式也由傳統(tǒng)的紙質(zhì)數(shù)據(jù)發(fā)展成為電子數(shù)據(jù)?；ヂ?lián)網(wǎng)技術(shù)的發(fā)展促進了網(wǎng)絡(luò)資源的共享與傳播，數(shù)據(jù)量呈現(xiàn)一種爆炸式增長的模式，數(shù)據(jù)數(shù)量并不代表數(shù)據(jù)質(zhì)量，如何在大量數(shù)據(jù)中找到有用的數(shù)據(jù)，如同在沙漠中挖掘鉆石，這給數(shù)據(jù)清洗集成和數(shù)據(jù)挖掘帶來了挑戰(zhàn)。相似性連接技術(shù)作為數(shù)據(jù)清洗集成等技術(shù)中的重要步驟[1]，同樣面臨著大數(shù)據(jù)的挑戰(zhàn)。在數(shù)據(jù)清洗集成中，相似性連接技術(shù)是對不同數(shù)據(jù)源或者同源的實體記錄，根據(jù)定義相似度度量函數(shù)獲取記錄對的相似度，將所有滿足相似度閾值的記錄對進行相似性連接，得到所有相似的記錄對，而相似性連接搜索查詢是利用相似性連接技術(shù)，對給定查詢對象，查詢數(shù)據(jù)集中滿足相似度閾值的所有記錄[2]。

隨著數(shù)據(jù)量的激增，面向大數(shù)據(jù)的相似性連接技術(shù)無論是在數(shù)據(jù)大規(guī)模存儲還是在數(shù)據(jù)處理速度上，實現(xiàn)基于相似性連接技術(shù)的應(yīng)用功能都更加具有挑戰(zhàn)性?？紤]到大數(shù)據(jù)存儲效率和執(zhí)行效率兩方面因素，基于單機計算的計算模式已經(jīng)不適合處理大規(guī)模數(shù)據(jù)了，因此面向大數(shù)據(jù)的相似性連接技術(shù)由單機計算逐漸發(fā)展成為面向集群計算和分布式計算。越來越多的研究人員采用分布式存儲系統(tǒng)和分布式計算框架作為面向大數(shù)據(jù)相似性連接的解決方案。一方面，對于相似連接，利用傳統(tǒng)數(shù)據(jù)庫中Join操作很難達到相似性連接計算的要求，這是因為連接條件并不是現(xiàn)有數(shù)據(jù)庫中的一個易于執(zhí)行的操作，需要進行相似度計算對兩條記錄進行近似連接。另一方面，為了保證大量數(shù)據(jù)的相似性連接的計算效率，主要解決方案是將傳統(tǒng)的單機集中式計算替換為使用集群計算或者分布式計算，例如分布式計算框架Hadoop、Storm、Spark等。

目前相似性連接技術(shù)主要分為兩個階段，過濾階段和確認階段[3]。過濾階段是通過一定的過濾規(guī)則過濾掉一定不滿足相似度閾值的記錄對，減少候選集合中記錄對的數(shù)量，減少網(wǎng)絡(luò)傳輸，提高相似性連接效率。將不能直接過濾的記錄對在確認階段進行最終確認，即可得到滿足相似度閾值的記錄對，進而得到相似性連接關(guān)系。因此提高過濾階段的效率，是相似性連接技術(shù)的核心問題。

前綴過濾技術(shù)是基于元素（token）相似性連接技術(shù)中較為普遍適用的過濾算法。文獻[1]對不同相似性連接技術(shù)進行了較為全面的分析，在處理大規(guī)模數(shù)據(jù)并且相似度閾值較高時，基于位置信息的前綴過濾算法PPJoin+[4]具有良好的表現(xiàn)。但是PPJoin+側(cè)重于后綴位置信息的應(yīng)用，針對現(xiàn)有過濾技術(shù)特別是使用位置信息過濾的方法不能充分利用前后綴之間token的位置信息這一不足，本文結(jié)合記錄前綴與另一條記錄后綴中存在共同元素的特點以及基于權(quán)重相似度計算的情況，進行如下研究：

（1）利用文本記錄中共同前綴之后的第一個元素在另一條記錄后綴位置的信息，提出了雙綴過濾方法PSFiltering，并且基于PSFiltering實現(xiàn)分布式相似性連接PSJoin。

（2）結(jié)合基于權(quán)重相似度計算的特點和雙綴過濾方法基本原理，利用元素本身權(quán)重大小實現(xiàn)過濾，提出了基于權(quán)重的雙綴過濾方法WTPSFiltering，并且基于WTPSFiltering實現(xiàn)分布式相似性連接WTPSJoin。

（3）針對本文算法和前人算法從過濾效果、執(zhí)行時間和加速比三方面進行比較和分析，從而驗證本文算法的有效性。

本文組織結(jié)構(gòu)如下：第2章討論了相似性連接的相關(guān)工作；第3章介紹了過濾原理以及基于Spark的分布式相似性連接；第4章詳細介紹了雙綴過濾原理以及利用雙綴過濾實現(xiàn)基于Spark的分布式相似性連接算法；第5章討論了雙綴過濾原理在權(quán)重相似度計算中的應(yīng)用，并實現(xiàn)了分布式計算；第6章給出實驗結(jié)果，并對實驗結(jié)果進行分析；最后對全文加以總結(jié)。

2 相關(guān)工作

相似性連接算法的過濾方法主要包括基于特征標簽（signature）和基于樹（tree）。基于signature的相似性連接過濾算法有長度過濾（length filtering）、計數(shù)過濾（count filtering）、前綴過濾（prefix filtering）等。在前綴過濾基礎(chǔ)上，結(jié)合不同的相似度度量函數(shù)，提出了很多相關(guān)算法。在Jaccard相似度方面，文獻[5]提出了有序記錄前綴過濾解決方案，集合所有記錄中的元素都要求按照某種全局序G進行排序，計算前綴長度，根據(jù)前綴中的元素建立倒排索引表，同一個元素的倒排索引中的記錄就形成候選集；文獻[6]提出AllPairs利用相似字符串自身長度或者集合大小進一步進行過濾，從而達到減小候選集的目的，通常基于Jaccard相似連接時會使用到大小過濾；文獻[7]提出利用有序記錄中元素的位置信息估算相似度上限值，通過比較估算上限與兩條記錄必須滿足的閾值條件來獲取候選集；文獻[4]在此基礎(chǔ)上提出了PPJoin以及PPJoin+；文獻[8]針對相似性連接提出了一種Adaptive框架，通過估算代價選取不同前綴長度，減少相似性連接執(zhí)行時間，該方法在處理大規(guī)模數(shù)據(jù)時性能較好，但是自適應(yīng)階段構(gòu)建索引代價較大，不適合應(yīng)用到基于前綴過濾的分布式計算中。在編輯距離方面，文獻[9]利用不匹配（q-grams）提出了位置信息過濾和內(nèi)容過濾兩種優(yōu)化技術(shù)的Edjoin；不同于Ed-join，QChunk[10]增加了一個過濾特征（q-chunks），降低了用于估算邊界值的signature數(shù)量。

除此之外，文獻[11]提出了Top-K相似性連接算法，返回K對最相似的記錄對，此算法不需要設(shè)定相似度閾值；基于樹的相似連接算法包括TrieJoin[12]和M-Tree[13]等。

文獻[1]在進行較為全面分析的基礎(chǔ)上總結(jié)出，在大規(guī)模數(shù)據(jù)和選取較大相似度閾值時，PPJoin+具有良好的特性。同時PPJoin+能夠較好地擴展到Hadoop等分布式計算環(huán)境中[14]。

3 基于Spark計算的分布式相似性連接

3.1 相似性連接過濾原理

過濾是相似性連接算法的核心部分。過濾階段針對不同的相似度函數(shù)選取不同的過濾方法。本文所提到的相似性連接是基于集合相似度的相似性連接。常見集合相似度為覆蓋相似度Overlap和杰卡德相似度Jaccard，二者定義和關(guān)系如式（1）～式（3）所示。

根據(jù)不同的相似度函數(shù)以及相似度函數(shù)之間的關(guān)系可以得到不同的前綴計算公式。假設(shè)α為Overlap的閾值，t為Jaccard的閾值，那么可得到記錄s的Overlap前綴長度為|S|-α+1，s的Jaccard前綴長度為。前綴過濾是分布式計算的理論依據(jù)，通過建立倒排索引表，在同一個key中的記錄就是滿足前綴過濾條件的記錄。前綴過濾計算可以進行分割計算和合并計算，滿足分布式計算條件，因此相似性連接可以實現(xiàn)分布式計算。

3.2 基于Spark的分布式相似性連接算法

針對MapReduce等計算模型中出現(xiàn)的不足[15]，伯克利大學推出了大數(shù)據(jù)處理框架Spark[16]，其核心為彈性分布式數(shù)據(jù)集（resilient distributed datasets，RDD）。Spark每次對RDD操作后的結(jié)果，都可以存放到內(nèi)存中，下一個RDD操作可以直接從內(nèi)存中讀取數(shù)據(jù)作為輸入，省去了MapReduce計算中大量的HDFS交互。結(jié)合RDD特點，使用Spark框架實現(xiàn)分布式相似性連接既具有理論依據(jù)又具有應(yīng)用價值。文獻[14]提出基于MapReduce的相似性連接分布式算法，在此基礎(chǔ)上，改寫成為基于Spark的分布式相似性連接，其RDD轉(zhuǎn)換圖如圖1所示。

Fig.1 RDD transformations of distributed prefix filtering on Spark圖1 基于Spark分布式前綴過濾RDD轉(zhuǎn)換操作圖

為了進一步闡釋問題，假設(shè)選取論文實體中的title作為連接屬性，如圖1所示，從HDFS等分布式文件系統(tǒng)中讀入數(shù)據(jù)，轉(zhuǎn)化為可被Spark識別并處理的RDD數(shù)據(jù)形式，讀入數(shù)據(jù)為RDD[String]類型，稱之為InputRDD，對InputRDD中進行map轉(zhuǎn)換，對每條記錄使用split方法進行切分，獲取記錄唯一id以及連接屬性；該階段結(jié)束后形成mapRDD，類型為RDD[(String,String)]，mapRDD通過轉(zhuǎn)換操作flatmap根據(jù)每條記錄的前綴建立倒排索引，形成flatmapRDD[(String,String)]；此時將mapRDD和flatmapRDD進行Join轉(zhuǎn)換操作，將兩個形如(key,value)鍵值對的RDD進行連接，獲得title，形成JoinRDD[(String,(String,String))]；對于JoinRDD進行g(shù)roupBykey轉(zhuǎn)換操作，相同key值下面的記錄就是滿足前綴過濾條件的記錄，在groupBykey中對相同key下面的記錄計算相似度，得到最終結(jié)果，對結(jié)果RDD進行存儲。在分布式計算基礎(chǔ)上，對于同一個key下面的記錄同樣需要過濾方法來避免笛卡爾積運算，如圖中虛線框所示，構(gòu)造二次過濾方法，以達到減少候選集合大小的目的。

4 基于雙綴過濾的相似性連接算法

4.1 雙綴過濾原理

目前已有的基于集合的過濾方法中，均是在前綴過濾基礎(chǔ)上進行再次過濾，相比較于前綴過濾等方法，這些改進方法都可以達到良好的過濾效果，如PPJoin和PPJoin+中的過濾機制。PPJoin和PPJoin+均是利用對有序記錄的位置信息實現(xiàn)有效的過濾，分別利用前綴和前綴、后綴和后綴中元素的位置信息估計相似度上限值。但是如果一條記錄前綴中的token出現(xiàn)在另一條記錄的后綴中，那么同樣基于位置信息，討論記錄s的前綴（prefix）和記錄r的后綴（suffix）之間元素位置關(guān)系對估算相似度上限值的影響。因此提出基于雙綴（前綴-后綴）過濾算法PSFilteringing（pefix-suffix filtering）。由于解決問題需要，方法中所提到的后綴不是真正計算得到的后綴，而是記錄對中前綴最后一個共同元素之后的所有元素。

如圖2所示，記錄s和記錄r的前綴分別為p1和p2，后綴分別為q1和q2，其中元素B是p1和p2中最后一個共同元素，取前綴p1中元素B之后的第一個元素C作為掃描元素scanning-token，對r的后綴進行掃描，獲取元素C在q2中的位置信息。因為記錄s和r都是按照統(tǒng)一個序G作為標準進行排序，并且記錄s的長度大于r的長度，所以p1中C之后出現(xiàn)的元素一定是C在序G之后的元素。同理，記錄r的后綴中元素C之后的元素也是排在C之后的元素，由此可知，記錄r中B之后和C之前的元素不會出現(xiàn)在s中，因此這一部分不可能成為相似度上限upbound的一部分。而對于記錄s和r中C之后的所有元素，其最大的覆蓋度為兩者之間token數(shù)量較小者。最終s和r的upbound如式（4）所示：

Fig.2 PSFiltering with scanning-token in recordr圖2 雙綴過濾（記錄r中存在掃描元素）

其中，prec表示前綴中共同元素個數(shù)。

s中元素B之后的部分均稱為混合后綴。掃描元素也是混合后綴中第一個元素。在特殊情況下，掃描元素也有可能是后綴中的第一個元素：

當記錄s的掃描元素在記錄r中不存在時，如圖3所示，只需要比較s記錄中掃描元素之后部分與記錄r的混合后綴，選取較小長度作為上限的組成部分。式（5）計算的是該種情況下的上限。

Fig.3 PSFiltering without scanning-token inr圖3 雙綴過濾（記錄r中不存在掃描元素）

根據(jù)過濾方法描述，PSFiltering實現(xiàn)偽代碼如函數(shù)1描述。其中函數(shù)1描述的是PSFiltering過濾算法，即描述該記錄對中混合后綴部分的相似度上限估算，記錄s的混合后綴為Mix1，r混合后綴為Mix2。函數(shù)1中第1行取混合后綴中的第一個元素作為掃描元素；第2～4行計算在記錄r中存在掃描元素情況下的上限值；第6行計算在記錄r中不存在掃描元素的上限值。其中take函數(shù)表示取該位置包括該位置之前的所有元素，drop函數(shù)表示取該位置之后的所有元素。

函數(shù)1PSFiltering混合后綴覆蓋相似度上限計算upbound(Mix1,Mix2,q2）

功能：估算記錄對覆蓋相似度上限

輸入：有序字符串Mix1,Mix2和q2

輸出：估算覆蓋上限upbound

1.scanning-token=Mix1.get(first)

2.pos=q2.getpos(scanning-token)

3.if(pos.exist)

4.return 1+min(Mix1.drop(first),q2.drop(pos))

5.else

6.return 1+min(Mix1.drop(first),Mix2)

7.end if

算法1描述的是過濾方法PSFiltering。第1～2行根據(jù)參數(shù)獲取記錄前綴；第3行獲取較短記錄的后綴q2；第4行取前綴共同元素個數(shù) prec；第5行取前綴中最后一個共同元素；第6～7行分別獲取共同元素之后的混合后綴；第8行計算記錄s和r的覆蓋相似度下限，通過比較上限值與必須滿足的最小覆蓋相似度大小，判斷該記錄對是否可以成為候選記錄對，進而進行確認階段的計算。

算法1雙綴過濾PSFiltering(s,r,t)

功能：基于雙綴有序記錄對過濾

輸入：記錄對s和r，以及Jaccard閾值t輸出：滿足閾值相似記錄對

1.p1=s.getprefix(t)

2.p2=r.getprefix(t)

3.q2=r.getsuffix(t)

4.prec=p1∩p2//取記錄對s和r的前綴的交集

5.lastc=(p1∩p2).getlasttoken

6.Mix1=mixSuffix(s,lastc)

7.Mix2=mixSuffix(r,lastc)

8.up=prec.size+upbound(Mix1,Mix2,q2)

9.if(up≥(s.size+r.size)×t/(1+t))

10.verify(s,r)

11.end if

4.2 基于雙綴過濾的分布式相似性連接算法

根據(jù)第3.2節(jié)中基于Spark分布式前綴過濾相似性連接RDD轉(zhuǎn)換操作圖，實現(xiàn)基于雙綴過濾的相似性連接PSJoin。如圖4所示，該圖與圖1相似，但不同之處在groupBykey階段。該圖描述了PSJoin在Spark數(shù)據(jù)流處理過程。圖4通過groupBykey對記錄進行聚集，實現(xiàn)PSFiltering過濾，在確認階段計算實際相似度，得到最終結(jié)果并進行存儲。

5 基于雙綴過濾的權(quán)重相似性連接算法

5.1 權(quán)重相似度過濾原理

在現(xiàn)有的基于覆蓋相似度度量中，絕大多數(shù)計算均假設(shè)記錄中的元素對于區(qū)分相似程度的貢獻在數(shù)值上是相同的。例如，覆蓋相似度中，每一個元素的貢獻度均相等。但是，不同的元素對記錄之間的相似度貢獻度不一樣，貢獻度稱為權(quán)重，文獻[4]提到了基于覆蓋相似度的權(quán)重相似度計算。假設(shè)對每一個token都有一個權(quán)重的賦值，定義wt(e)表示e詞語的權(quán)重，式（6）表示基于覆蓋相似度的權(quán)重相似度計算：

Fig.4 Data processsing in distributed PSJoin圖4 分布式PSJoin數(shù)據(jù)流程圖

同時文獻[4]提出了基于覆蓋相似度的過濾方法，如圖5所示，對于記錄s，設(shè)基于權(quán)重的Overlap相似度閾值為α，那么該記錄的前綴權(quán)重之和最低為 β1=Wt(s)-α，因為記錄中的元素分割不是以每個token作為一個分割體，而是以一個token并且附帶著權(quán)重(weight)的形式出現(xiàn)并且劃分的，所以在計算取前綴token時，前綴中所有的token的權(quán)重之和剛好大于 β1。

Fig.5 Weighted ordering records圖5 有序權(quán)重記錄

假設(shè) prefixβ1(s)表示記錄s的前綴元素token集合。如果 WtO(s?r)≥α，則 prefixβ1(s)?prefixβ2(r)≠?。如果前綴中沒有交集，即 prefixβ1(s)?prefixβ2(r)=?，那么s和r記錄的WtO(s?r)＜α。

式（7）為基于Jaccard的權(quán)重相似度計算[1]。設(shè)WtJ(S,R)閾值為t，則有式（8）。其證明過程類似于Overlap閾值與Jaccard閾值關(guān)系證明[4]。

權(quán)重作為基于權(quán)重相似度計算中的重要部分，其計算具有十分重要的意義。對文本進行基于權(quán)重的相似度計算時，由于相同的詞具有相同的權(quán)重值，本文使用無序過程中的權(quán)重賦值逆文本頻率指數(shù)（inverse document frequency，IDF）。

5.2 基于雙綴過濾的權(quán)重相似性連接原理

現(xiàn)有的基于權(quán)重計算的過濾算法中，文獻[4]實現(xiàn)了基于PPJoin+的權(quán)重相似性連接。本文在第2章提出了利用前綴與后綴之間共同元素位置關(guān)系的過濾方法PSFiltering。結(jié)合權(quán)重相似度的特點，利用PSFiltering的過濾思想，本文提出雙綴過濾方法的權(quán)重相似性連接WTPSFiltering（weighted PSFiltering）。

如圖6所示，記錄s和r分別表示帶有權(quán)重的記錄，并且記錄中的token按照權(quán)重由大到小進行排序，獲取記錄的前綴集合。p1和p2分別表示記錄s和記錄r的前綴集合，q1和q2分別表示記錄s和記錄r的后綴集合。prec表示前綴交集大小，wtsumprec表示前綴交集中元素權(quán)重和，如圖6，prec=1即為元素A，wtsumprec=0.7。不同于PSFiltering，為了達到更好的過濾效果，利用元素的權(quán)重而不是元素本身進行比較，也就是說，不需要考慮元素本身，僅需要該元素的權(quán)重值。權(quán)重在某種程度上也是一種“序”，權(quán)重的大小可以表示token的一種排序關(guān)系，對于權(quán)重相等的token，可能不是同一個token，但是對于同一個token，它的權(quán)重一定相等。如圖6所示，A作為前綴中最后一個token，為了更加準確地估計記錄s和記錄r的覆蓋相似度的上限upbound，需要利用A后面元素scanning-token的權(quán)重信息作為過濾條件。

Fig.6 WTPSFiltering圖6 WTPSFiltering方法

以圖6為例，取記錄s的前綴中最后一個common token之后的第一個元素，該元素在記錄s中的位置為i，權(quán)重為0.5，此時，只需要關(guān)注該元素的權(quán)重，利用權(quán)重大小對記錄r的common token之后的所有元素進行掃描，過濾出所有權(quán)重小于等于0.5的token。假設(shè)r中j位置之后的元素的權(quán)重都是小于或者等于0.5的，對于j之前和A之后的元素的權(quán)重都是大于0.5且小于0.7的，因此這期間元素是不可能對upbound有貢獻的。除了前綴中的common token，另一部分就是k1和k2中權(quán)重之和較小的作為upbound的一部分。因此基于權(quán)重過濾上限由式（9）計算可得，其中wt表示元素權(quán)重或者集合中所有元素權(quán)重和。

選擇權(quán)重信息作為過濾條件與選擇token本身相比，能夠加強過濾效果。這是因為如果選取記錄s中的common token之后的token本身信息作為掃描元素，需要考慮在記錄r中是否存在該元素。但是對于選取權(quán)重信息作為過濾條件，可以有效地避免scanning-token不存在的情況，只需要比較大小就可以選取記錄中小于等于掃描元素權(quán)重的所有元素，不需要做其他比較。

基于權(quán)重過濾改進算法WTPSFiltering描述如算法2所示。第5行描述取記錄s中的最后一個common token位置，如圖6中A的位置；同理第6行取記錄r中的最后一個common token位置；第7～8行分別取記錄s和記錄r中的common token之后第一個token,scanning-token1和scanning-token2。比較 scanningtoken1和scanning-token2權(quán)重大小，選取權(quán)重較小者作為掃描元素，這樣可以最大限度地降低混合后綴權(quán)重之和大小，使上限估計值更貼近真實值，過濾效果更好。

算法2雙綴權(quán)重過濾算法WTPSFiltering(s,r,t)

功能：基于記錄中權(quán)重信息實現(xiàn)有序記錄對過濾

輸入：記錄對s和r，以及WtJ閾值t

輸出：該記錄對是否滿足閾值限定條件

1.p1=s.getprefixw(t)

2.p2=r.getprefixw(t)

3.prec=p1?p2//取記錄對s和r的前綴的交集

4.wtsumprec=prec.wt

5.pos1=s.getpos(prec.last)//取前綴交集最后位置

6.pos2=r.getpos(prec.last)

7.scantoken1=s.get(pos1+1)

8.scantoken2=r.get(pos2+1)

9.if(scantoken1.wt＜scantoken2.wt)

10. k2=r.filter(≤scantoken1.wt)

11. up=wtsumprec+min(s.drop(pos1).wt,k2.wt)

12.else

13. k1=r.filter(≤scantoken2.wt)

14.up=wtsumprec+min(r.drop(pos2).wt,k1.wt)

15.end if

16.if(up≥(s.wt+r.wt)×t/(1+t))

17.verify(s,r)

18.end if

5.3 基于雙綴過濾的分布式權(quán)重相似性連接算法

不同于雙綴過濾的分布式相似性連接，權(quán)重相似性連接在計算過程中需要附加權(quán)重信息。利用Spark實現(xiàn)基于WTPSFiltering的權(quán)重相似性連接WTPSJoin，其RDD轉(zhuǎn)換如圖7所示。其中有兩個輸入，一個輸入是需要處理的文本string，以論文的id和title為例，另一輸入是所有title中token的權(quán)重。map轉(zhuǎn)換動作中是將記錄中title的每一個token賦予相應(yīng)的權(quán)重并且按照權(quán)重值由大到小進行排序，生成（id,title-weight）形式RDD。在flatmap中應(yīng)用權(quán)重信息計算前綴權(quán)重和，并且根據(jù)前綴建立倒排索引。通過 join將兩個key值相同的RDD連接在一起，返回用于分組的數(shù)據(jù)形式(token,(id,title-weight)),在groupByKey階段聚集相同的token，使用過濾算法WTPSFiltering進行過濾得到候選集。

Fig.7 RDD transformations of WTPSJoin on Spark圖7 基于Spark WTPSJoin的RDD轉(zhuǎn)換圖

6 實驗結(jié)果與分析

本文所有算法的實現(xiàn)使用編程語言scala，滿足分布式Spark編程需求。本文實驗環(huán)境使用10個Slaver節(jié)點和1個Master節(jié)點的Hadoop作為分布式文件的存儲環(huán)境，構(gòu)建了10個Worker節(jié)點和1個Master節(jié)點的Spark集群。

節(jié)點環(huán)境如下：

（1）CPU：Intel?XeonE5-2620CPU@2.0GHz；

（2）內(nèi)存：32 GB DDR RAM；

（3）硬盤：8 TB；

（4）操作系統(tǒng)：Fedora Linux。

集群環(huán)境版本如下：

（1）Hadoop集群版本為Hadoop-1.0.4；

（2）Spark集群版本為Spark-1.0.0；

（3）Java版本為1.6.0_43。

相對于分詞技術(shù)，本文側(cè)重于對算法效率進行研究，因此實驗中所使用的測試數(shù)據(jù)集為EI論文數(shù)據(jù)集以及少量DBLP數(shù)據(jù)集和Citeseerx數(shù)據(jù)集等英文數(shù)據(jù)集。其中用于測試PSJion的數(shù)據(jù)格式為id-title文件，包括DBLP（162 MB）、EI（262 MB）、Citeseerx（100 MB）。用于測試WTPSJoin的數(shù)據(jù)格式為idabstract文件，主要利用EI（370 MB）數(shù)據(jù)集中的摘要進行權(quán)重相似性連接。本文數(shù)據(jù)集是在項目研發(fā)過程中通過網(wǎng)絡(luò)爬取獲得的，為了驗證算法在大量數(shù)據(jù)下的效果，對原始數(shù)據(jù)進行了統(tǒng)計以及隨機擴充，對數(shù)據(jù)中出現(xiàn)的所有詞建立詞表，隨機抽取詞表中一定數(shù)量詞對原始數(shù)據(jù)進行循環(huán)擴充，擴充3種數(shù)據(jù)集的混合數(shù)據(jù)集為1.4 GB，與擴充前相比，相似記錄對比例會發(fā)生變化，數(shù)據(jù)集里依然存在大量的相似數(shù)據(jù)。本文實驗主要測試算法過濾效果、執(zhí)行時間以及加速比。

（1）過濾效果

如圖8所示，該圖描述的是id-abstract數(shù)據(jù)集在不同閾值情況下利用權(quán)重PPJoin+、WTPSJoin過濾之后的數(shù)據(jù)集大小以及真正滿足Result集合大小。橫坐標為不同的相似度閾值，相似度閾值分別為0.85、0.90和0.95?？v坐標為集合大?。ê蜻x集數(shù)據(jù)對數(shù)量），包括候選集合大小和結(jié)果集合大小。

Fig.8 Candidate size in different weighted similarity join with different threshold圖8 不同閾值下不同權(quán)重相似性連接算法候選集大小

圖9描述的是id-title混合數(shù)據(jù)集（1.4 GB）在不同閾值情況下利用PPJoin、PPJoin+、PSJoin過濾后數(shù)據(jù)集大小?？梢钥闯鯬SJoin的過濾效果明顯好于其他兩種算法。表1為該數(shù)據(jù)滿足相似度閾值的記錄對數(shù)量。

Fig.9 Candidate size in different similarity join with different threshold圖9 不同閾值下不同相似性連接算法候選集大小

Table1 Record pairs with similarity over threshold表1 滿足相似度閾值數(shù)據(jù)對數(shù)量

由圖8、圖9可知，從整體上看候選集合大小隨著相似度閾值的增加會變少。無論是基于雙綴過濾的PSJoin還是基于雙綴過濾的權(quán)重相似性連接WTPSJoin，與PPJoin+相比均有較好的過濾效果，能將大量不必要數(shù)據(jù)對過濾掉，以降低候選集合大小，提高計算效率。

（2）不同算法執(zhí)行時間

執(zhí)行時間包括建立倒排索引時間、相似性連接時間、過濾時間和候選集合確認時間。

如圖10所示，僅僅對比了效果較好的PPJoin+權(quán)重相似性連接與WTPSJoin。在不同的相似度閾值時，WTPSJoin的執(zhí)行時間均低于PPJoin+權(quán)重相似性連接。隨著相似度閾值的增加，算法之間的執(zhí)行時間差異越來越小。

圖11是PPJoin、PPJoin+以及PSJoin這3種相似性連接對數(shù)據(jù)量為1.4 GB的id-title文件的執(zhí)行時間。同圖10類似，隨著相似度閾值的增加，3種連接算法執(zhí)行時間均有減少，但PSJoin的執(zhí)行時間始終少于其他算法。與此同時，各種過濾算法的執(zhí)行時間的差異也越來越小。

（3）加速比對比

圖12描述了不同算法隨著節(jié)點個數(shù)增加對idtitle文件相似性連接執(zhí)行時間的變化。節(jié)點個數(shù)由2個增加到10個，相似度閾值取0.90，隨著節(jié)點個數(shù)增加，所有算法執(zhí)行時間均降低，PSJoin執(zhí)行時間始終低于其他算法。

圖13為不同算法隨著節(jié)點個數(shù)變化的加速比（即2節(jié)點時間/當前節(jié)點個數(shù)時間）。由圖可知，隨著節(jié)點數(shù)量增加，通信代價增加，與理想加速比差距增大，總體來講PSJoin具有較好的加速比。

通過實驗可以得到以下結(jié)論：

（1）雙綴過濾方法可以達到良好的過濾效果，與現(xiàn)有的相似性連接算法相比執(zhí)行時間較少。

Fig.10 Time cost in different weighted similarity join with different threshold圖10 不同閾值不同權(quán)重相似性連接算法執(zhí)行時間對比

Fig.11 Time cost in different similarity join with different threshold圖11 不同閾值不同相似性連接算法執(zhí)行時間對比

（2）基于WTFiltering的方法具有良好的過濾效果，執(zhí)行時間也少于集合相似度（區(qū)別于編輯距離等其他相似度度量）PPJoin+的執(zhí)行時間。

（3）PSJoin具有良好的加速比。

Fig.12 Time cost on different cluster size圖12 不同節(jié)點數(shù)量相似性連接算法執(zhí)行時間

Fig.13 Speedup圖13 加速比

7 總結(jié)

本文以Spark計算框架為基礎(chǔ)，利用RDD計算實現(xiàn)分布式相似性連接。針對基于前綴過濾的PPJoin和PPJoin+中忽略前后綴之間的關(guān)聯(lián)這一不足，提出了PSJoin相似性連接算法和基于權(quán)重相似性連接的WTPSJoin。其中，PSJoin利用不同記錄前綴和后綴中第一個common token的位置信息實現(xiàn)過濾。WTPSJoin是利用記錄對前綴之間common token之后的第一個元素的權(quán)重大小與另一條記錄后綴元素權(quán)重大小之間關(guān)系實現(xiàn)過濾。同時，PSJoin具有良好的加速比。本文相似性連接算法中使用的過濾方法在擴充混合數(shù)據(jù)集合上性能表現(xiàn)良好，從理論上分析，本文過濾方法在記錄前綴中共同元素之后的元素出現(xiàn)在另一條記錄后綴中偏后位置時性能最佳，并且過濾方法可以根據(jù)原理應(yīng)用到不同的計算平臺。

在未來工作中，一方面結(jié)合不同的相似度度量函數(shù)的特點，例如編輯距離等，將基于位置信息的雙綴過濾以及權(quán)重過濾進行擴展；另一方面，對權(quán)重過濾中的權(quán)重獲取以及權(quán)重更新問題進行研究。

[1]Jiang Yu,Li Guoliang,Feng Jiahua.String similarity joins:an experimental evaluation[J].Proceedings of the VLDB Endowment,2014,7(8):625-636.

[2]Pang Jun,Gu Yu,Xu Jia,et al.Research advance on similarity join queries[J].Journal of Frontiers of Computer Science and Technology,2013,7(1):1-13.

[3]Chaudhuri S,Ganti V,KaushikR.Aprimitive operator for similarity joins in data cleaning[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA,Apr 3-7.Washington:IEEE Computer Society,2006:5.

[4]Xiao Chuan,Wang Wei,Lin Xuemin,et al.Efficient similarity joins for near-duplicate detection[J].ACM Transactions on Database Systems,2011,36(3):15.

[5]Sarawagi S,KirpalA.Efficient set joins on similarity predicates[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,Paris,Jun 13-18,2004.New York:ACM,2004:743-754.

[6]BayardoR J,Ma Yiming,SrikantR.Scaling up all pairs similarity search[C]//Proceedings of the 16th International Conference on World Wide Web,Banff,Canada,May 8-12,2007.New York:ACM,2007:131-140.

[7]Lin Xuemin,Wang Wei.Set and string similarity queries:a survey[J].Chinese Journal of Computers,2011,34(10):1853-1862.

[8]Wang Jiannan,Li Gguoliang,Feng Jianhua.Can we beat the prefix filtering?an adaptive framework for similarity join and search[C]//Proceedings of the 2012ACM SIGMOD International Conference on Management of Data,Scottsdale,USA,May 20-24,2012.NewYork:ACM,2012:85-96.

[9]Chuan Xiao,Wang Wei,Lin Xuemin.Ed-Join:an efficient algorithm for similarity joins with edit distance constraints[J].Proceedings of theVLDB Endowment,2008,1(1):933-944.

[10]Qin Jianbin,Wang Wei,Lu Yifei,et al.Efficient exact editsimilarity query processing with the asymmetric signature scheme[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Greece,Jun 12-16,2011.NewYork:ACM,2011:1033-1044.

[11]Xiao Chuan,Wang Wei,Lin Xuemin,et al.Top-k set similarity joins[C]//Proceedings of the 25th International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEE Computer Society,2009:916-927.

[12]Wang Jiannan,Feng Jianhua,Li Guoliang.Trie-join:efficient trie-based string similarity joins with edit-distance constraints[J].Proceedings of the VLDB Endowment,2010,3(1/2):1219-1230.

[13]Ciaccia P,Patella M,Zezula P.M-tree:an efficient access method for similarity search in metric spaces[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,Athens,Greece,Aug 26-29,1997.San Francisco,USA:Morgan Kaufmann Publishers Inc,1997:426-435.

[14]VernicaR,Carey M J,Li Chen.Efficient parallel set-similarity joins using MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010.New York:ACM,2010:495-506.

[15]Xia Junluan,Liu Xuhui,Shao Saisai,et al.Big data processing technologies on Spark[M].Beijing:Publishing House of Electronics Industry,2015.

[16]Zaharia M,Chowdhury M,Franklin M J,et al.Spark:cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing,Boston,USA,Jun 22-25,2010.Berkeley,USA:USENIX Association,2010:10.

附中文參考文獻：

[2]龐俊,谷峪,許嘉,等.相似性連接查詢技術(shù)研究進展[J].計算機科學與探索,2013,7(1):1-13.

[7]林學民,王煒.集合和字符串的相似度查詢[J].計算機學報,2011,34(10):1853-1862.

[15]夏俊鸞,劉旭輝,邵賽賽,等.Spark大數(shù)據(jù)處理技術(shù)[M].北京:電子工業(yè)出版社,2015.

Big Data Similarity Join Processing Based on Prefix-Suffix Filtering*

DENG Shizhuo,XIN Junchang,NIE Tiezheng,WANG Guoren+
School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:wanggr@mail.neu.edu.cn

DENG Shizhuo,XIN Junchang,NIE Tiezheng,et al.Big data similarity join processing based on prefix-suffix filtering.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1235-1245.

Similarity join is one of the key techniques in entity identification and data integration which are significant for detecting valuable information.With the development of big data,it cannot satisfy the demand of efficiency to do the job on one machine.As a consequence,distributed computation becomes a better choice to improve the execution efficiency of similarity join.This paper gets a deeper understanding of processing algorithms for distributed similarity join based on Spark.Since the method using only suffix positional information for filtering has some shortcomings,this paper proposes a distributed similarity join processing method PSJoin,which uses the common token positional information between the prefix of one record and the suffix of another one.Also PSJoin can be applied to the weighted case with a little change for weight tokens.It compares the weight of the first token in the mix-suffix of one record with the weights of the tokens in the other record.The weighted similarity join with PSJoin is called WTPSJoin which improves the processing efficiency.The two new methods provide novel and efficient solutions for similarity join of big data.Experiments are tested on mixed datasets,and results show that the proposed algorithms have better performance in filtering,less running time cost and perfect speedup.

similarity join;weighted similarity join;big data;filtering;Spark

ang was born in 1977.He

the Ph.D.degree from Northeastern University in 2008.Now he is an associate professor at Northeastern University.His research interests include uncertain data management,big data management and analysis,etc. 信俊昌（1977—），男，遼寧遼陽人，2008年于東北大學獲得博士學位，現(xiàn)為東北大學計算機科學與工程學院副教授，主要研究領(lǐng)域為不確定數(shù)據(jù)管理，大數(shù)據(jù)管理分析等。

DENG Shizhuo was born in 1990.She is a Ph.D.candidate at Northeastern University.Her research interest is big data management and analysis.鄧詩卓（1990—），女，遼寧凌源人，東北大學博士研究生，主要研究領(lǐng)域為大數(shù)據(jù)管理與分析。

NIE Tiezheng was born in 1980.He is an associate professor at Northeastern University.His research interests include data integration,XML data management,NoSQL database system,entity resolution and data analysis for big data,etc.聶鐵錚（1980—），男，遼寧沈陽人，東北大學計算機科學與工程學院副教授，主要研究領(lǐng)域為數(shù)據(jù)集成管理，XML數(shù)據(jù)管理，NoSQL數(shù)據(jù)庫系統(tǒng)，大數(shù)據(jù)實體解析與分析等。

WANG Guoren was born in 1966.He received the Ph.D.degree from Northeastern University in 1996.Now he is a full professor and Ph.D.supervisor at School of Computer Science and Engineering,Northeastern University,and the member of CCF.His research interests include cloud computing,XML data management,data stream analysis,high-dimensional indexing and P2P data management,etc.王國仁（1966—），男，湖北崇陽人，1996年于東北大學獲得博士學位，現(xiàn)為東北大學計算機科學與工程學院教授、博士生導師，CCF會員，主要研究領(lǐng)域為云計算，XML數(shù)據(jù)管理，數(shù)據(jù)流分析，高維索引，P2P數(shù)據(jù)管理等。

A

：TP316

*The National Natural Science Foundation of China under Grant Nos.61402089,61472069,61502215(國家自然科學基金);the Fundamental Research Funds for the Central Universities of China under Grant No.N150408001(中央高校基本科研業(yè)務(wù)費專項資金);the Natural Science Foundation of Liaoning Province under Grant No.2015020553(遼寧省自然科學基金).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.016.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1235-11

10.3778/j.issn.1673-9418.1608045

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

摘 要：相似性連接技術(shù)是實體識別和數(shù)據(jù)集成的關(guān)鍵技術(shù)之一，是挖掘數(shù)據(jù)中有價值信息的重要手段。隨著大數(shù)據(jù)發(fā)展，傳統(tǒng)的集中式相似性連接已經(jīng)無法滿足人們對數(shù)據(jù)處理的時效性需求，并且利用分布式計算可以提高相似性連接的執(zhí)行效率。因此，深入研究了基于Spark的分布式相似性連接處理算法。針對僅使用后綴位置信息過濾方法的不足，提出了利用一條記錄前綴與另一條記錄后綴間共同元素位置信息來進行過濾的分布式相似性連接PSJoin，提高了相似性連接的處理效率，減少了相似性連接的執(zhí)行時間。同時，針對基于權(quán)重的相似度連接算法的過濾問題，結(jié)合雙綴過濾原理，通過一條記錄前綴共同元素之后的第一個元素的權(quán)重與另一條記錄后綴中元素權(quán)重大小的關(guān)系，提出了基于雙綴過濾的分布式權(quán)重相似性連接WTPSJoin。為面向大數(shù)據(jù)的相似性連接計算提供了兩種可靠的解決方案。兩種算法在多數(shù)據(jù)源混合數(shù)據(jù)集上進行測試實驗，實驗結(jié)果表明，所提算法相對于已有的過濾算法過濾效果好，執(zhí)行時間少，同時具有良好的加速比。