王曉霞,孫德才
(渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院,錦州 121013)
隨著互聯(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é)果顯示本算法獲得了較高的連接效率。
Q-sample 算法的定義是:給定二個字符串集R,S和一個編輯距離閾值τ,相似連接算法的主要目的是在集合R和集合S間找出所有滿足相似要求的字符串對。為實現(xiàn)相似連接,設(shè)計了四個MapReduce 階段,即統(tǒng)計階段、過濾階段、驗證階段1和驗證階段2。
統(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中以備后用。
過濾階段的主要任務(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對,即
在過濾階段,產(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ū)分輸入的來源。如果是候選集,則無需處理直接原樣輸出,即
map:
map:< sn,split> →
在shuffle 過程中,具有相同sid的key-value對被傳送到同一個reduce 結(jié)點上。在reduce 過程中,輸入也是一個key-value對
reduce:
在驗證階段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 對
map:<(sid,v#s),list(rid) > →
map:< sn,split> →
在reduce 中將通過驗證每個候選對的方法找出真正相似對。在一個reduce 任務(wù)中,輸入是一個key-value 對
實驗中用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)。
實驗中使用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處理中提高處理速度。
本文主要研究大數(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)用中有實際意義。