大數據處理中MapReduce框架的Q-sample算法設計

王曉霞，孫德才

（渤海大學信息科學與技術學院，錦州 121013）

0 引言

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

1 基于Q-sample和統計特征的相似連接算法

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

1.1 統計階段

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

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

在shuffle 過程中，把map 過程中產生的所有具有相同key 的key-value 對傳輸到同一個reduce結點上。

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

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

1.2 過濾階段

過濾階段的主要任務是生成子串和得出候選對集，同樣包含map、shuffle 和reduce 三個過程。在一個map 任務內根據數據的來源不同進行不同的處理。對于輸入的兩個集合R,S，如果輸入的key-value 對來源于集合R，將為集合生成索引子串。如果輸入的key-value 對來源于集合S，將為集合生成匹配子串。首先字符串的編號sid和內容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從循 環到。在每次循環中，邏輯上把字符串s用q分割成連續但不重疊的qsample，而此時只需為第i個q-sample生成匹配子串的位置psj限制在范圍［max（0，（i-1）q-t），min（（i-1）q+t，s-q）］內，如圖1所示。

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

而當q≤2τ+ 1時，此時所有q-gram都是有效的，所以不必為每個q-sample 計算生成q-gram。此時，map:< sn,split>→在shuffle 過程中具有相同key 的key-value 對被傳輸到同一個reduce 結點上。在reduce 過程中，輸入是一個key-value對，即。首先遍歷列表中的每個value，根據value 中的值可以區分出來是索引子串還是匹配子串，索引子串被加入到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

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

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

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

map: →

map:< sn,split> →

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

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

1.4 驗證階段2

在驗證階段1結束后，候選集中屬于集合S的串內容被保留，此時，因為缺少候選對中屬于集合R串的內容，所以仍然無法進行驗證。過濾階段2的主要任務是讀取候選集對屬于集合R中串的內容、為集合R中串生成統計向量和驗證候選對。在輸出的m個q-gram 集G[i],0 ≤i≤m- 1 被讀入并構建。驗證階段2 的map 過程的輸入包括集合R和驗證階段1 的輸出。在每個map 任務中，首先判斷輸入key-value 對的來源。如果來源是集R中的字符串r，則按驗證階段1 中方法為其生成統 計 向 量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 任務中，輸入是一個key-value 對。首先，列表list((sid,v#s)/('R',u#r))中的項被依次處理，如項是'R',u#r，則取出u和r。否則處理的項是sid,v#s，則把sid,v#s直接加入到一個列表slist中。所有項處理完成后，如slist 為空時，則該re?duce 任務無候選對；否則，循環處理slist 中的每個sid,v#s。對于每個sid,v#s，首先從中取出sid、v和s。然后計算如δ(u,v) >qτ，如果一不是一個候選對，直接拋棄，如果是一個候選對，則采用文獻［6］中的驗證方法進行驗證，以確定是否是滿足要求的相似對。

2 實驗

2.1 實驗環境

實驗中用Java 基于Hadoop 1.2.1 平臺實現了算法Q-sample。本文實驗數據來源于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/）三個數據集。三個數據集的詳情對比如表1。

表1 數據集信息

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

2.2 實驗結果

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

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

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

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

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

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

3 結語

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