一種基于MapReduce的局部相似自連接算法

王曉霞，孫德才

(渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121013)

0 引 言

隨著各行各業(yè)數(shù)據(jù)量的飛速增長，大數(shù)據(jù)的存儲(chǔ)、處理、管理和分析等領(lǐng)域已成為當(dāng)前研究的熱點(diǎn)。在大數(shù)據(jù)處理中，數(shù)據(jù)清洗的目的是刪除冗余信息、糾正存在的錯(cuò)誤等。相似連接(similarity join)[1-4]能在給定的數(shù)據(jù)集中快速找出所有滿足相似要求的記錄對，是數(shù)據(jù)清洗中去除相似信息的常用方法。相似連接在基因序列比對、剽竊檢測和信息檢索等領(lǐng)域也有廣泛的應(yīng)用。

相似連接分為全局連接和局部連接。全局連接要求記錄對的整體相似，而局部連接則要求記錄對滿足局部相似要求即可。相似連接又根據(jù)參與連接的數(shù)據(jù)源數(shù)分為自連接和多源連接。當(dāng)數(shù)據(jù)源為單個(gè)時(shí)稱為自連接，自連接找出的相似記錄對都來源于同一個(gè)數(shù)據(jù)集。而當(dāng)數(shù)據(jù)源為兩個(gè)及以上時(shí)稱為多源連接，多源連接的相似記錄對分別來源于不同的數(shù)據(jù)集。在相似連接中，衡量一個(gè)記錄對的相似程度的方法主要包括編輯距離[5-6]、海明距離、Jaccard、Cosine和Dice等。編輯距離是指把一個(gè)字符串經(jīng)過插入、修改或刪除三種編輯操作轉(zhuǎn)變成另一個(gè)字符串所要進(jìn)行的最小操作次數(shù)。文中用編輯距離衡量字符串對的相似度，因?yàn)榫庉嬀嚯x不僅對噪聲魯棒性強(qiáng)，還能體現(xiàn)出兩個(gè)字符串間字符順序的差別[6]。

研究相似連接算法的主要目的是加快相似連接的速度，尤其是基于大數(shù)據(jù)集的相似連接。當(dāng)前的相似連接算法主要有內(nèi)存算法和并行算法。內(nèi)存算法由于運(yùn)行過程中允許共享大量信息(如索引等)，所以只能運(yùn)行在單臺(tái)機(jī)器上，如PassJoin[7]、K-Join[8]和LS-Join[9]等。并行算法的設(shè)計(jì)目的是實(shí)現(xiàn)集群多任務(wù)并行計(jì)算，但并行算法也有共享信息困難的問題。MapReduce框架是Google提出的一種高效的分布式編程框架，在大數(shù)據(jù)處理中應(yīng)用廣泛。近年來，基于MapReduce框架的相似連接并行算法[6,10-15]的研究也得到了眾多學(xué)者的關(guān)注，如V-SMART-Join[10]、PassJoinKMR[6]、MassJoin[11]、SAX[14]、FS-Join[15]等。

文中研究的主要內(nèi)容是基于單個(gè)字符串集的局部相似自連接并行算法。目前，LS-Join算法是首個(gè)基于兩個(gè)數(shù)據(jù)集的局部相似連接內(nèi)存算法，雖然文中也提出了改進(jìn)的多線程算法，但仍無法實(shí)現(xiàn)集群多節(jié)點(diǎn)的并行計(jì)算。另外，在當(dāng)前的相關(guān)文獻(xiàn)中也尚未發(fā)現(xiàn)局部相似自連接算法的相關(guān)研究。對此，文中提出一種新的基于MapReduce框架的并行連接算法，并擬解決局部相似自連接的定位問題。

1 局部相似自連接及新過濾方案

1.1 局部相似自連接的問題定義

給定一個(gè)數(shù)據(jù)集，局部相似自連接將找出集合中所有存在局部相似的記錄對。這里先給出相關(guān)問題的定義：

定義2(局部相似自連接的定位問題)：給定一個(gè)窗口長度l、一個(gè)編輯距離參數(shù)τ和一個(gè)字符串集S。局部相似自連接的定位問題是從字符串集S中找出所有存在l-τ局部相似的串對,si∈S,sj∈S,i≠j，并同時(shí)找出該串對中最長的局部相似子串位置。

表1 例子字符串集

如給定一個(gè)字符串集S，如表1所示。數(shù)據(jù)集中每行是一個(gè)字符串的信息，其中‘#’號(hào)前面的是字符串編號(hào)，而后面的是字符串內(nèi)容。如l=7,τ=1，則是一個(gè)l-τ局部相似對，它們間如最長子串對為ed(s1[4,12],s3[1,9])=1。

1.2 局部相似自連接過濾方案

局部相似自連接的輸入包括一個(gè)給定的數(shù)據(jù)集、一個(gè)窗口長度和一個(gè)編輯距離參數(shù)。LS-Join算法[9]是一種基于兩個(gè)數(shù)據(jù)集的多源局部相似連接算法。LS-Join算法先讀取第一個(gè)字符串集并建立一個(gè)倒排索引。然后把第二個(gè)字符串集中的字符串拆分子串，并在倒排索引中檢索子串并生成候選串對。最后，提出了一種基于雙向擴(kuò)展的局部驗(yàn)證方法來驗(yàn)證候選對。該算法也能進(jìn)行自連接運(yùn)算，只需輸入的兩數(shù)據(jù)集相同即可。但如此連接后，結(jié)果集中存在兩種冗余記錄對，即自身冗余對和正反冗余對。自身冗余對為字符串和本身組成的串對，該串對中因兩字符串完全一樣，所以一定存在于結(jié)果集中，即,si∈S,sj∈S,i=j。正反冗余串對是兩個(gè)不同編號(hào)的字符串組成的串對，但因分先后順序而形成的冗余，如,si∈S,sj∈S,i≠j和,si∈S,sj∈S,i≠j。這些冗余串對不僅增加了連接算法計(jì)算的時(shí)間，還增加了結(jié)果集的數(shù)量。

因給定的數(shù)據(jù)集中含有大量的字符串，因此也存在著海量的字符串對。為避免枚舉所有串對，文中算法采用了過濾驗(yàn)證二階段模式。為進(jìn)行快速過濾和去除冗余對，該算法采用了基于分割子串的過濾方案。

定理1(無關(guān)對過濾定理)：給定兩個(gè)字符串si,sj，一個(gè)編輯距離參數(shù)τ和一個(gè)窗口長度l。把串si分割成?|si|/q」個(gè)連續(xù)但不重疊的長度為q的子串(稱為Q-sample)，其中q=?(l+1)/(τ+2)」,q≥1。此時(shí)如字符串對為l-τ局部相似對，則串sj中包含至少一個(gè)串si的Q-sample。

定理2(冗余對過濾定理)：給定一個(gè)字符串集S，一個(gè)編輯距離參數(shù)τ和一個(gè)窗口長度l。字符串集S中有兩個(gè)字符串si,sj，其中i為字符串si在集合S中的編號(hào)和j為sj的編號(hào)，則字符串對集G={,i

證明：在局部相似自連接中，有兩種冗余串對，即自身串對和正反串對。條件i

2 基于MapReduce框架的局部相似自連接算法

局部相似自連接的輸入包括：一個(gè)字符串集S，一個(gè)編輯距離參數(shù)τ和一個(gè)窗口長度l。為實(shí)現(xiàn)并行計(jì)算，文中的MLSSJ算法采用了分布式編程框架MapReduce，共設(shè)計(jì)了三個(gè)階段，即過濾階段、驗(yàn)證階段1和驗(yàn)證階段2。

2.1 過濾階段

為避免枚舉所有可能的字符串對，該算法設(shè)計(jì)了一個(gè)MapReduce任務(wù)實(shí)現(xiàn)無關(guān)對和冗余對的快速過濾方案。定理1是一個(gè)無關(guān)對過濾條件，使用定理1能拋棄那些不共享Q-sample的字符串對。定理2是一個(gè)冗余對過濾條件，使用定理2能拋棄影響連接性能的冗余對。為使用定理1和定理2進(jìn)行快速過濾，MLSSJ算法在過濾階段先對輸入的字符串集S中所有字符串進(jìn)行子串分割，然后再進(jìn)行過濾。過濾階段的MapReduce任務(wù)包括三個(gè)過程，即Map、Shuffle和Reduce。

(1)Map過程：基于MapReduce框架設(shè)計(jì)的程序執(zhí)行中并行交替運(yùn)行著眾多的map任務(wù)，每次map任務(wù)的輸入是一個(gè)key-value對，其中sn是分片的編號(hào)，而split是輸入字符串集S的一行內(nèi)容。例如表1中的例子集合，一次map的split就是一行內(nèi)容，即一個(gè)字符串的編號(hào)和內(nèi)容。為進(jìn)行局部相似自連接的前期處理，該算法先提取字符串的編號(hào)(記為sid)和字符串內(nèi)容(記為s)，然后針對字符串s分別生成索引子串和匹配子串，具體過程如下：

(2)Shuffle過程：在MapReduce框架中，shuffle過程將map過程產(chǎn)生的所有key-value對按key值(索引子串和匹配子串)進(jìn)行混淆、排序，并把具有相同key的key-value對送到同一reduce節(jié)點(diǎn)上。

2.2 驗(yàn)證階段1

過濾階段輸出結(jié)果由大量的key-value對構(gòu)成，其中每個(gè)key-value對都是一個(gè)候選對集，即一個(gè)key-value對包含了某個(gè)字符串與集S中所有編號(hào)小于該串的候選對。而驗(yàn)證階段的任務(wù)是從這些候選對集中找出真正含有局部相似的串對，并定位最長相似子串的位置。但現(xiàn)在因候選對集只有串編號(hào)而沒有串內(nèi)容，所以算法無法驗(yàn)證。為實(shí)現(xiàn)候選對集字符串內(nèi)容的快速讀取配對和驗(yàn)證候選對，該算法把驗(yàn)證階段設(shè)計(jì)成了兩個(gè)階段，即驗(yàn)證階段1和驗(yàn)證階段2。

驗(yàn)證階段1的主要目的是讀取集S的字符串內(nèi)容，并初步進(jìn)行字符串編號(hào)和串內(nèi)容的配對。它的輸入包括集S和過濾階段的輸出結(jié)果。驗(yàn)證階段1的MapReduce任務(wù)也包含Map、Shuffle和Reduce三個(gè)過程。

2.3 驗(yàn)證階段2

驗(yàn)證階段1結(jié)束后實(shí)現(xiàn)了大編號(hào)串編號(hào)和串內(nèi)容的匹配，也給出了每個(gè)大編號(hào)串對應(yīng)的候選對集，還輸出了需要保留的小編號(hào)串內(nèi)容。但此時(shí)仍無法進(jìn)行候選對的驗(yàn)證工作，因?yàn)檫€缺少小編號(hào)串的串內(nèi)容。驗(yàn)證階段2的任務(wù)是實(shí)現(xiàn)小編號(hào)串編號(hào)和串內(nèi)容的配對，同時(shí)進(jìn)行最終的驗(yàn)證定位工作。驗(yàn)證階段2的輸入是驗(yàn)證階段1輸出結(jié)果。驗(yàn)證階段2依然包含Map、Shuffle和Reduce三個(gè)過程。

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

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

為驗(yàn)證文中算法和相關(guān)技術(shù)的有效性，實(shí)驗(yàn)中基于MapReduce框架用Java實(shí)現(xiàn)了文中的MLSSJ算法。算法運(yùn)行環(huán)境為Hadoop集群，集群中主節(jié)點(diǎn)1個(gè)，從節(jié)點(diǎn)4個(gè)；硬件配置均為CPU i5 4590 四核心、16 G內(nèi)存和1 TB硬盤。實(shí)驗(yàn)中還實(shí)現(xiàn)了文獻(xiàn)[9]中的LS-Join算法，這里記LSJ-S為單線程算法，記LSJ-M為多線程算法(線程數(shù)為4)。實(shí)驗(yàn)的數(shù)據(jù)主要來源于兩個(gè)數(shù)據(jù)集，見表2。DBLP集是一個(gè)計(jì)算機(jī)類英文文獻(xiàn)的集成數(shù)據(jù)庫，實(shí)驗(yàn)中只保留了記錄中作者和標(biāo)題兩個(gè)字段。GBEST集為NCBI GenBank的表達(dá)序列標(biāo)簽(Expressed Sequence Tags, ftp://ftp.ncbi.nlm.nih.gov/)，實(shí)驗(yàn)中只保留了序列本身。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息

3.2 算法性能對比及結(jié)果分析

評價(jià)相似連接算法時(shí)，時(shí)間性能最為重要。LS-Join算法實(shí)驗(yàn)中的最優(yōu)配置參數(shù)DBLP集為l=50,τ=5,q=7，GBEST集為l=100,τ=7,q=9。MLSSJ算法的配置參數(shù)除不需要q值外其他與LS-Join算法相同。首先在實(shí)驗(yàn)中對比不同大小數(shù)據(jù)集對各算法性能的影響。實(shí)驗(yàn)中分別采用LSJ-S、LSJ-M和MLSSJ算法在不同大小的字符串集分別進(jìn)行局部相似自連接運(yùn)算，并統(tǒng)計(jì)了各個(gè)算法自連接的時(shí)間消耗。隨著字符串集字符串?dāng)?shù)量的逐漸增大，各算法的總連接時(shí)間變化如圖1和圖2所示。

圖1 DBLP集大小與連接時(shí)間

由圖1和圖2可知，隨著數(shù)據(jù)集中字符串?dāng)?shù)量的不斷增大，LSJ-M算法的連接速度一直快于LSJ-S算法，由此可見多線程并發(fā)技術(shù)加快了LS-Join算法的連接速度。MLSSJ算法的連接速度要明顯快于LS-Join的LSJ-S算法和LSJ-M算法，尤其在小字母表且長字符串的數(shù)據(jù)集(如GBEST)上新算法性能表現(xiàn)更優(yōu)。這主要是因?yàn)長S-Join算法是一個(gè)內(nèi)存算法，雖然采用了多線程技術(shù)但也只能運(yùn)行在一臺(tái)機(jī)器上。而MLSSJ算法是一個(gè)運(yùn)行在多節(jié)點(diǎn)集群上的并行算法，基于MapReduce框架的設(shè)計(jì)使得它更適合大數(shù)據(jù)集的局部相似自連接。從圖中還可以看出，隨著數(shù)據(jù)集的增大，MLSSJ算法的連接時(shí)間基本呈線性增加。

圖2 GBEST集大小與連接時(shí)間

在相似連接中，編輯距離參數(shù)是一個(gè)非常重要的參數(shù)。為對比各個(gè)算法對編輯距離參數(shù)的敏感度，實(shí)驗(yàn)中還分別采用不同的編輯距離參數(shù)對LSJ-M算法和MLSSJ算法在各數(shù)據(jù)集上進(jìn)行了局部相似自連接操作。在DBLP集上配置參數(shù)為l=50,τ=0,1,3,5(LSJ-M中q=7)， GBEST集上為l=100,τ=0,1,3,5,7(LSJ-M中q=9)。隨著編輯距離參數(shù)的逐漸增大，各算法的性能表現(xiàn)對比如圖3和圖4所示。

圖3 DBLP集編輯距離與連接時(shí)間

圖4 GBEST集編輯距離與連接時(shí)間

由圖3和圖4可知，在不同編輯距離參數(shù)下MLSSJ算法的速度一直快于LSJ-M算法。該實(shí)驗(yàn)主要分析各個(gè)算法對編輯距離參數(shù)的敏感度。由圖3和圖4可知，LSJ-M算法隨著編輯距離參數(shù)不斷增大而連接時(shí)間變化較小，因此該算法對編輯距離參數(shù)的敏感度較小。這主要是因?yàn)閷?shí)驗(yàn)中LSJ-M算法的索引子串長度q值對不同編輯距離參數(shù)影響較大，而這里q值固定。實(shí)際使用中需要對不同數(shù)據(jù)集進(jìn)行q值實(shí)驗(yàn)測優(yōu)，因此該算法也不夠靈活。而MLSSJ算法隨著編輯距離參數(shù)的不斷增大，其連接時(shí)間也不斷增加，因此該算法對編輯距離參數(shù)的敏感度較大。這主要是因?yàn)镸LSSJ算法中切分子串長度是根據(jù)編輯距離參數(shù)動(dòng)態(tài)計(jì)算的，即τ值越小，q值越大，分割得到的子串?dāng)?shù)目越少，處理所需的時(shí)間就越短。因此，MLSSJ算法在編輯距離參數(shù)動(dòng)態(tài)變化的局部相似自連接中比LSJ-M算法更具優(yōu)勢。

4 結(jié)束語

文中主要研究了基于單個(gè)字符串集的局部相似自連接算法。先給出了局部相似自連接定位問題的定義，然后通過分析相似自連接中的無關(guān)串對和冗余串對問題，總結(jié)出了無關(guān)串對過濾定理和冗余串對過濾定理。最后提出了一種基于MapReduce框架的局部相似自連接并行算法。實(shí)驗(yàn)結(jié)果表明，該算法有效地提高了局部相似自連接的速度。該算法雖然通過MapReduce框架的并行技術(shù)加快了局部相似自連接的速度，但仍存在并行節(jié)點(diǎn)間數(shù)據(jù)傳輸量大和過濾階段生成的候選對多等問題。下一步將研究更加苛刻的過濾條件，擬通過降低過濾階段生成的候選對數(shù)量來減少驗(yàn)證時(shí)間。