大數(shù)據(jù)處理中MapReduce框架的Q-sample算法設(shè)計

王曉霞，孫德才

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

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，各行各業(yè)數(shù)據(jù)量也急速增長，傳統(tǒng)的數(shù)據(jù)處理方式已不能滿足要求，大數(shù)據(jù)以其在存儲、處理、管理和分析等方面的優(yōu)勢漸漸成為解決海量數(shù)據(jù)處理的有效工具［1-2］。而基于MapReduce 框架的相似連接技術(shù)在海量大數(shù)據(jù)分析中取得了重大進(jìn)展，已成為主流的大數(shù)據(jù)分析技術(shù)［3］。近年來，大量的重復(fù)數(shù)據(jù)導(dǎo)致MapReduce 的混淆消耗過大［4］，同時也導(dǎo)致網(wǎng)絡(luò)傳輸?shù)膿矶?。為提高基于編輯距離的相似連接算法速度，本文提出了一種基于MapReduce 的雙集合全局相似連接算法Q-sample，力圖通過減少MapReduce 框架的混淆消耗和網(wǎng)絡(luò)傳輸來提高連接效率。通過真實數(shù)據(jù)集的實驗，結(jié)果顯示本算法獲得了較高的連接效率。

1 基于Q-sample和統(tǒng)計特征的相似連接算法

Q-sample 算法的定義是：給定二個字符串集R,S和一個編輯距離閾值τ，相似連接算法的主要目的是在集合R和集合S間找出所有滿足相似要求的字符串對。為實現(xiàn)相似連接，設(shè)計了四個MapReduce 階段，即統(tǒng)計階段、過濾階段、驗證階段1和驗證階段2。

1.1 統(tǒng)計階段

統(tǒng)計階段是統(tǒng)計集合中各個q-gram 的頻率和對q-gram 進(jìn)行m集合分類，輸入是一個樣例集合和q-gram 過濾器參數(shù)Q和統(tǒng)計向量長度限值m。統(tǒng)計階段包含map、shuffle和reduce三個過程。

Map 過程的任務(wù)是輸入一個key-value 對，key 是片段的編號sn，value 是片段的內(nèi)容。首先將value 拆分出字符串的內(nèi)容s，再把s從0到 |s|-Q拆分成固定長度為Q的連續(xù)且重疊Q-1 的q-gram，并輸出一個key-value對。

在shuffle 過程中，把map 過程中產(chǎn)生的所有具有相同key 的key-value 對傳輸?shù)酵粋€reduce結(jié)點上。

Reduce 過程中首先遍歷鏈表并統(tǒng)計列表中1的數(shù)目c。最后輸出一個key-value 對。

當(dāng)reduce 過程結(jié)束后，則統(tǒng)計出了樣例集合中所有q-gram 的頻率。為把所有q-gram 分散到m個集合中，即G[i],0 ≤i≤m- 1。本文采用文獻(xiàn)［5］的貪婪算法實現(xiàn)q-gram 的分配，得出各個分組的頻率總和接近。最后，輸出這m個q-gram 分組到DFS中以備后用。

1.2 過濾階段

過濾階段的主要任務(wù)是生成子串和得出候選對集，同樣包含map、shuffle 和reduce 三個過程。在一個map 任務(wù)內(nèi)根據(jù)數(shù)據(jù)的來源不同進(jìn)行不同的處理。對于輸入的兩個集合R,S，如果輸入的key-value 對來源于集合R，將為集合生成索引子串。如果輸入的key-value 對來源于集合S，將為集合生成匹配子串。首先字符串的編號sid和內(nèi)容s先從key-value 對的value 中抽取出來。如果字符串s與字符串r相似，即ed(r,s) ≤τ，則字符串s中一定包含至少一個字符串的索引子串。如果字符串s有多個子串。則字符串r和字符串s滿足 |r|<|s|-t或 |r|> |s|+t，則這二個字符串一定不是相似對。因此，為字符串s匹配子串時，只需考慮為那些滿足 |s|-τ≤|r|≤|s|+τ的r生成匹配子串。為生成字符串s的匹配串，我們先讓q從循 環(huán)到。在每次循環(huán)中，邏輯上把字符串s用q分割成連續(xù)但不重疊的qsample，而此時只需為第i個q-sample生成匹配子串的位置psj限制在范圍［max（0，（i-1）q-t），min（（i-1）q+t，s-q）］內(nèi)，如圖1所示。

圖1 一個固定q值下q-gram有效開始位置的范圍

而當(dāng)q≤2τ+ 1時，此時所有q-gram都是有效的，所以不必為每個q-sample 計算生成q-gram。此時，map:< sn,split>→在shuffle 過程中具有相同key 的key-value 對被傳輸?shù)酵粋€reduce 結(jié)點上。在reduce 過程中，輸入是一個key-value對，即。首先遍歷列表中的每個value，根據(jù)value 中的值可以區(qū)分出來是索引子串還是匹配子串，索引子串被加入到Ilist 列表中，而匹配子串被加入到Slist 中。處理完成后，如果這二個列表中某個為空，則代表該子串無候選對。否則，對于Ilist 中的每個索引子串和Slist 中的每個匹配子串形成的對就是一個潛在的匹配對，如 ，Ilist[i]=(rid, ||r,pri),Slist[j]=(sid, ||s,psj)。 此 時， 如 果 滿足>τ（Standard-Match 過濾器），則它一定不是一個τ匹配，直接拋棄即可。否則是一個候選對，把rid加到列表list(rid)中。最后，針對每個Slist[j]生成一個key-value對，即。

1.3 驗證階段1

在過濾階段，產(chǎn)生了包含R和S間所有潛在匹配對的候選集。但候選集中只有串的ID 號而沒有內(nèi)容，所以不能進(jìn)行驗證。采用文獻(xiàn)［6］中提出的二階段讀取方法實現(xiàn)R和S集合字符串內(nèi)容的讀取。驗證階段分為證階段1 和驗證階段2 兩個階段。

驗證階段1 的主要任務(wù)是讀取候選集中涉及到集S的串內(nèi)容、消除冗余串對和生成集S中串的統(tǒng)計向量。驗證階段1 包含map、shuffle 和re?duce 三個過程。在setup（執(zhí)行map 任務(wù)前）中，統(tǒng)計階段的輸出的m個q-gram集G[i],0 ≤i≤m- 1被讀入并構(gòu)建。

驗證階段1 的輸入包括集合S和過濾階段輸出的候選集。在一個map 任務(wù)中，首先區(qū)分輸入的來源。如果是候選集，則無需處理直接原樣輸出，即；如果是集S中的一個串，則先構(gòu)建一個長度為的全零向量v，然后從0開始到 |s|-Q處理每個q-gram。當(dāng)G[i]包含當(dāng)前q-gram 時，對v[i]增1；而當(dāng)某個q-gram 沒有出現(xiàn)在G中任何集中時，該q-gram 屬于樣例集中不存在的q-gram，則對G[m- 1]增1（認(rèn)為在最后一個集）。最后為當(dāng)前字符串s構(gòu)建了一個統(tǒng)計向量v，最后輸出一個key-value 對，即。這里‘#’是統(tǒng)計向量和串內(nèi)容的分隔。

map: →

map:< sn,split> →

在shuffle 過程中，具有相同sid的key-value對被傳送到同一個reduce 結(jié)點上。在reduce 過程中，輸入也是一個key-value對，該key-value 對包含了所有字符串s和集合R間是所有候選對。首先，構(gòu)造一個非重復(fù)集合L。然后依次處理列表list(list(rid)/(v#s))中的值，如果是v#s則存儲備用；否則是list(rid)，則遍歷每個rid并加入到L中。處理完成時，用L構(gòu)建一個列表list(rid)。當(dāng)列表list(rid)非空時輸出key-value 對<(sid,v#s),list(rid) >，否則什么也不輸出。

reduce: →<(sid,v#s),list(rid) >

1.4 驗證階段2

在驗證階段1結(jié)束后，候選集中屬于集合S的串內(nèi)容被保留，此時，因為缺少候選對中屬于集合R串的內(nèi)容，所以仍然無法進(jìn)行驗證。過濾階段2的主要任務(wù)是讀取候選集對屬于集合R中串的內(nèi)容、為集合R中串生成統(tǒng)計向量和驗證候選對。在輸出的m個q-gram 集G[i],0 ≤i≤m- 1 被讀入并構(gòu)建。驗證階段2 的map 過程的輸入包括集合R和驗證階段1 的輸出。在每個map 任務(wù)中，首先判斷輸入key-value 對的來源。如果來源是集R中的字符串r，則按驗證階段1 中方法為其生成統(tǒng) 計 向 量u， 并 輸 出 key-value 對。如果輸入是驗證階段1 的輸出key-value對<(sid,v#s),list(rid) >，則為列表中的每一個rid生成一個key-value對，即。

map:<(sid,v#s),list(rid) > →

map:< sn,split> →

在reduce 中將通過驗證每個候選對的方法找出真正相似對。在一個reduce 任務(wù)中，輸入是一個key-value 對。首先，列表list((sid,v#s)/('R',u#r))中的項被依次處理，如項是'R',u#r，則取出u和r。否則處理的項是sid,v#s，則把sid,v#s直接加入到一個列表slist中。所有項處理完成后，如slist 為空時，則該re?duce 任務(wù)無候選對；否則，循環(huán)處理slist 中的每個sid,v#s。對于每個sid,v#s，首先從中取出sid、v和s。然后計算如δ(u,v) >qτ，如果一不是一個候選對，直接拋棄，如果是一個候選對，則采用文獻(xiàn)［6］中的驗證方法進(jìn)行驗證，以確定是否是滿足要求的相似對。

2 實驗

2.1 實驗環(huán)境

實驗中用Java 基于Hadoop 1.2.1 平臺實現(xiàn)了算法Q-sample。本文實驗數(shù)據(jù)來源于DBLP au?thor+title（http://dblp.uni-trier.de/xml/）、GenBank EST（ftp://ftp.ncbi.nlm.nih.gov/genbank/）和PubMed abstract（ftp://ftp.ncbi.nlm.nih.gov/pubmed/baseline/）三個數(shù)據(jù)集。三個數(shù)據(jù)集的詳情對比如表1。

表1 數(shù)據(jù)集信息

實驗集群中的總節(jié)點數(shù)為5個（1個主節(jié)點，4個從節(jié)點），每個節(jié)點的硬件配置為：CPU i5 4590 3.7 GHZ，內(nèi)存16 G，硬盤1 TB。集群軟件配置：操作系統(tǒng)Ubuntu 15.10 64 位，Java 1.7，Hadoop 平臺版本1.2.1。為進(jìn)行雙集合相似連接實驗，先把數(shù)據(jù)集分割成2 個字符串?dāng)?shù)目相等的集合（R和S），然后在上述集群環(huán)境中采用算法對2個集合進(jìn)行相似連接。實驗中以編輯距離作為默認(rèn)的相似連接度量標(biāo)準(zhǔn)。

2.2 實驗結(jié)果

實驗中使用Q-sample 算法分別在DBLP（τ= 4）、GenBank EST（τ= 8）和PubMed abstract（τ= 20）數(shù)據(jù)集上進(jìn)行相似連接運算。采用不同q-gram 過濾器及組合時算法的驗證時間統(tǒng)計如圖2到圖4。

圖2 不同q-gram過濾器及組合DBLP

圖3 不同q-gram過濾器及組合GenBank EST

圖4 不同q-gram過濾器及組合PubMed

圖2 到圖4 展示了在三個不同數(shù)據(jù)集上Qsample 算法使用不同q-gram 過濾器和向量長度的驗證時間。如圖2—圖4 所示，過濾器（Q= 1）的驗證時間要一直少于其他q-gram 過濾器（Q= 2或Q= 3）。

從實驗結(jié)果可以看出，在所采用的三種數(shù)據(jù)集中，Q-sample 算法的時間都是最低的，使得在MapReduce處理中提高處理速度。

3 結(jié)語

本文主要研究大數(shù)據(jù)處理框架下基于MapRe?duce 框架的相似連接并行算法Q-sample。因為Q-sample 的子串生成方案減少了子串?dāng)?shù)量，所以算法的map 過程輸出量要降低，從而減少混淆時間和數(shù)據(jù)傳輸時間，因此過濾時間也減少了，而過濾時間的快慢大體上決定了從DFS 上讀取數(shù)據(jù)的時間消耗。 reduce 過程的輸出數(shù)據(jù)是候選集，采用了過濾驗證二階段模式。在驗證過程中，采用了多維的統(tǒng)計向量進(jìn)一步過濾掉了無效候選對，然后采用驗證算法對候選對進(jìn)行驗證，這樣則提高了過濾效率。實驗結(jié)果顯示算法可以解決大數(shù)據(jù)處理中的處理速度緩慢問題，在大數(shù)據(jù)應(yīng)用中有實際意義。