馮禹洪 吳坤漢 黃志鴻 馮洋洲 陳歡歡 白鑒聰 明 仲

1 （深圳大學(xué)計算機與軟件學(xué)院 廣東深圳 518060）

2 （中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 合肥 230027）（yuhongf@szu.edu.cn）

集合相似度自連接是大數(shù)據(jù)分析的重要操作，它是從一個集合集中找出相似度大于給定閾值的集合對，有著廣泛的應(yīng)用，如協(xié)同過濾[1]、檢測近似重復(fù)的網(wǎng)頁[2]、社交網(wǎng)絡(luò)分析[3]等.其中，度量2 個集合的相似度可根據(jù)應(yīng)用選擇合適的度量函數(shù)，如Jaccard函數(shù).

集合相似度自連接需要度量集合集中所有集合對的相似度，時間復(fù)雜度為O(kn2)， 其中n為集合集的大小，k為任意2 個集合相似度的平均計算時間.當(dāng)集合規(guī)模較大時，如2019 年第3 季度知名社交網(wǎng)絡(luò)平臺Facebook 的月活躍用戶人數(shù)為24.5 億[4]，每個用戶都有好友集合.Facebook 用戶好友集合的自連接計算中n=2.45×109，這樣的大規(guī)模數(shù)據(jù)集給時間復(fù)雜度高的集合相似度自連接計算帶來挑戰(zhàn).基于要處理的數(shù)據(jù)是靜態(tài)數(shù)據(jù)還是動態(tài)數(shù)據(jù)（流數(shù)據(jù)），現(xiàn)有集合相似度自連接計算方法可以劃分為2 類：批處理式計算和流處理式計算.

首先，批處理式集合相似度自連接計算要處理的是靜態(tài)數(shù)據(jù)，運行過程中沒有新增數(shù)據(jù).現(xiàn)有提高運行效率的批處理式集合相似度自連接計算方法可以劃分為2 類：近似計算方法和基于過濾-驗證框架的準(zhǔn)確計算方法.近似計算方法通過設(shè)計合適的集合相似度快速估算方法來加速計算，如基于位置敏感哈希函數(shù)的MSJL[5]、基于局部敏感過濾的LSFJoin[6]、基于高維數(shù)據(jù)速寫和索引的CPSJoin[7]等，但因估算降低了精度導(dǎo)致不能找出所有相似度超過閾值的集合對.本文將關(guān)注準(zhǔn)確計算方法.

基于過濾-驗證框架的準(zhǔn)確計算方法包括allpair[8], PPJoin[2], MPJoin[9], AdaptJoin[10], GroupJoin[11]等，其計算采用先過濾后驗證的2 階段計算方法.第1 階段使用合適的過濾策略將檢測發(fā)現(xiàn)的相似度低于閾值的集合對刪除，獲得較小的候選集；第2 階段基于規(guī)模減小后的候選集驗證并輸出相似度大于給定閾值的集合對，提高了效率.有效的過濾策略是提高這類算法的重要支撐技術(shù)，常用策略包含長度過濾[12]、前綴過濾[8]、位置過濾[2]等.最近提出的位圖過濾[13]采用哈希函數(shù)創(chuàng)建表達(dá)集合特征為固定長度的位圖，然 后通過位操作推斷集合對相似的上界，實現(xiàn)相對使用其他策略最高達(dá)4.50 倍的性能提升.

同時，并行分布式計算方法通過將大規(guī)模計算或數(shù)據(jù)劃分為一系列較小的分片，每個分片被分發(fā)到不同計算節(jié)點上并行運行以提高計算效率.根據(jù)計算節(jié)點的體系結(jié)構(gòu)，并行分布式集合相似度自連接計算可以劃分為基于GPU 的計算和基于CPU 的計算.基于GPU 的系列算法有效提升了集合相似度連接的計算性能[14]，但是，基于GPU 的實現(xiàn)需要對硬件有深入的了解，這往往需要編程者付出很高的學(xué)習(xí)成本.而基于CPU 的集群計算是更為普及的并行分布式計算，現(xiàn)有的基于CPU 的并行分布式集合相似度連接算法大部分基于MapReduce[15]框架.根據(jù)處理過程是否將集合切分為多段，基于MapReduce 框架和過濾-驗證框架的集合相似度連接算法可劃分為2 大類：1）集合整體過濾與驗證，這類算法包括RIDPairsPPJoin（下文簡稱為RP-PPJoin, 有些文獻(xiàn)也稱為VernicaJoin）[16]， MGJoin[17]，SSJ-2R[18]等；2）集合數(shù)據(jù)分段過濾與驗證，如FS-Join[19].第1 類算法將集合切分為多段，分段過濾，然后合并驗證.這類算法容易被理解，但存在同一集合多次重復(fù)驗證的現(xiàn)象.第2 算法避免了重復(fù)驗證.但當(dāng)閾值較低時，這2 類算法產(chǎn)生的候選集規(guī)模都比較大，運行效率并不理想[20].

其次，流處理式集合相似度自連接計算處理的是動態(tài)數(shù)據(jù)，該數(shù)據(jù)指的是隨時間依次產(chǎn)生的數(shù)據(jù)，如網(wǎng)絡(luò)監(jiān)控數(shù)據(jù)、氣象測控等.其數(shù)據(jù)量隨著時間增長，顯著特征是數(shù)據(jù)有時間戳，能快速生成.集合流處理計算通?；谂幚碛嬎惴椒?，引入集合相似度時間衰減因子、采樣降低數(shù)據(jù)量從而提高計算效率，如串行式計算的基于PPJoin 設(shè)計的流處理計算算法SSTR[21]、基于更新日志的遞增式流處理計算算法ALJoin[22]等，分布式計算的流處理計算算法BundleJoin[23]和KNN Join[24]等.

綜上所述，面向靜態(tài)數(shù)據(jù)基于MapReduce 的并行分布式集合相似度自連接計算效率無論對批處理式計算還是流處理式計算都很重要，本文擬采用頻繁模式樹（frequent pattern tree, FP-tree）[25]，通過用更緊湊的擴展前綴樹結(jié)構(gòu)表示數(shù)據(jù)并壓縮到內(nèi)存中處理，減小生成的候選集的規(guī)模，同時減少I/O 操作，降低后續(xù)計算復(fù)雜度.本文將系統(tǒng)地研究FP-tree 及其派生結(jié)構(gòu)FP-tree*，設(shè)計針對集合相似度自連接計算更有效的FP-tree*，并設(shè)計相應(yīng)的基于MapReduce 框架的并行分布式集合相似度自連接算法.本文的主要貢獻(xiàn)有3 點：

1）提出面向集合相似度自連接的遍歷效率更高的線性頻繁模式樹 TELP-tree（traversal efficient linear prefix tree）結(jié)構(gòu)模型及基于它的集合相似度自連接算法TELP-SJ，該算法包括2 階段過濾算法，減小樹的規(guī)模和減少對樹結(jié)點的遍歷，降低集合對相似度計算和驗證的時空復(fù)雜度；

2）設(shè)計基于TELP-tree 和MapReduce 的并行分布式集合相似度自連接算法FastTELP-SJ；

3）基于4 組真實應(yīng)用數(shù)據(jù)集進(jìn)行3 組性能比較實驗，分別進(jìn)行TELP-SJ 算法與其他基于FP-tree*的算 法，如FastTELP-SJ，TELP-SJ，F(xiàn)astTELP-SJ 等 和 現(xiàn)有其他基于 MapReduce 算法的比較，本文實驗結(jié)果展現(xiàn)了FastTELP-SJ 算法在處理高維大規(guī)模集合相似度自連接計算時的性能優(yōu)于其他算法.

1 基于FP-tree 的集合相似度自連接算法

給定集合集x={x1,x2,…,xn} ， 任意xi,xj∈x，xi和xj都是集合，集合相似度度量函數(shù)sim(xi,xj) ，閾值t，x的集合相似度自連接是找出所有滿足sim(xi,xj)≥t的集合對 (xi,xj).

為方便討論，本文以Facebook 開放的大規(guī)模應(yīng)用數(shù)據(jù)集Facebook applications dataset II[26]的部分?jǐn)?shù)據(jù)為例，演示基于其構(gòu)建的FP-tree 派生結(jié)構(gòu)，面向集合相似度自連接計算存在的問題及后續(xù)算法的處理過程.示例數(shù)據(jù)如圖1 的X所示，其中uid代表用戶標(biāo)識號，aid代表應(yīng)用標(biāo)識號.在示例數(shù)據(jù)的應(yīng)用場景中，uid和aid可以分別被理解為集合標(biāo)識號和元素標(biāo)識號.對任一用戶ui，其使用的應(yīng)用可表示為集合A(ui) ，如A(u1)={a1,a2,a3,a4,a5}.如式（1）所示，當(dāng)集合A(ui)和A(uj)的 相 似 度sim(A(ui),A(uj))用Jaccard(A(ui),A(uj)) 來 計 算 時，sim(A(u1),A(u3))=3/(5+3-3)=0.6.

Fig.1 Transpose of sample data圖1 示例數(shù)據(jù)轉(zhuǎn)置

FP-tree 數(shù)據(jù)結(jié)構(gòu)最初用于挖掘頻繁模式，為使用它來計算集合相似度自連接，我們首先要將其中集合交集大小的計算轉(zhuǎn)化為基于頻繁二項模式挖掘的計算.為此，轉(zhuǎn)置X的行與列得到X′的 數(shù)據(jù)，X中任意2 個集合A(ui)和A(uj)的 交集大小 |A(ui)∩A(uj)|的計算就轉(zhuǎn)換成X′中二項集 (ui,uj)出 現(xiàn)的頻次fi,j[27]的計算.如X′中 二項集 (u1,u3) 出現(xiàn)的頻次f1,3=3,示例數(shù)據(jù)中|A(u1)∩A(u3)|=|{a1,a2,a3}|=3，f1,3=|A(u1)∩A(u3)|.另外，X′中 一項集ui出 現(xiàn)的頻次與X中的 |A(ui)|出現(xiàn)的頻次也相等.

1.1 FP-tree 及其派生結(jié)構(gòu)

FP-tree 是一種擴展前綴樹結(jié)構(gòu)，該樹保留了所有項集的關(guān)聯(lián)信息，基于FP-tree 可以遞歸地挖掘出所有的頻繁項集[25].FP-tree 數(shù)據(jù)結(jié)構(gòu)模型由2 部分組成：頭表和樹結(jié)構(gòu).頭表由三元組表示（元素，頻次，頭指針），其中“頭指針”指向樹結(jié)構(gòu)中元素相同的第1 個結(jié)點，頭表中的三元組按照頻次遞減排序.樹結(jié)構(gòu)結(jié)點由六元組表示（元素，頻次，計數(shù)，父結(jié)點指針，子結(jié)點指針，下一個元素相同結(jié)點的指針），其中“計數(shù)”指的是共同前綴出現(xiàn)頻次的計數(shù)，“下一個元素相同結(jié)點的指針”用于構(gòu)建索引鏈，把樹中具有相同元素的結(jié)點鏈接起來.

構(gòu)建FP-tree 包括構(gòu)建頭表H和樹結(jié)構(gòu).X′中任一應(yīng)用ai的 用戶集合標(biāo)記為U(ai)，U(ai)元素按照頻次降序排序的序列標(biāo)記為S(ai).首先初始化頭表和樹結(jié)構(gòu)，將數(shù)據(jù)集中所有ui及 其一項頻次fi按照頻次倒序加入頭表中，相應(yīng)頭指針L(ui)初始化為空指針，即索引鏈為空；而樹結(jié)構(gòu)則初始化為元素為空的根結(jié)點.然后將X′中 任一應(yīng)用ai相應(yīng)的序列S(ai)插入頭表和樹結(jié)構(gòu)中.對任一序列S(ai)，假設(shè)當(dāng)前始于根且與S(ai) 有 最長共同前綴的路徑為P，則給共同前綴上所有結(jié)點的計數(shù)都加1，將S(ai)中不在共同前綴中的元素依序插入樹中，同時結(jié)點ui鏈接到對應(yīng)元素的索引鏈的末尾.基于圖1 示例數(shù)據(jù)構(gòu)建的FP-tree 見圖2（a）.為了簡化圖2 表示，樹結(jié)點信息僅展示其中的3 項，并以三元組格式展示（元素, 頻次, 計數(shù)）.

Fig.2 Construction of the FP-tree, N-lists, LP-tree, and TELP-tree over the sample data圖2 基于示例數(shù)據(jù)構(gòu)建的FP-tree, N-lists, LP-tree, TELP-tree

構(gòu)建好FP-tree 后，簡單的集合相似度自連接可以通過以下流程完成：首先根據(jù)頭表結(jié)點索引鏈遍歷樹并統(tǒng)計所有包含這些結(jié)點元素的二項集出現(xiàn)頻次，即相應(yīng)集合交集大??；然后驗證2 個集合相似度是否大于閾值；最后輸出大于閾值的集合對.其中統(tǒng)計樹二項集的頻次時取二項計數(shù)值中較小者累加.例如，從頭表的u3開始，索引項的第1 個樹結(jié)點是(u3,3,3) ，沿分支向根結(jié)點方向遍歷并統(tǒng)計包含u3的二項集的頻次.其中 (u3,3,3;u1,5,5)的二項計數(shù)值較小者為3， (u3,3,3;u1,5,5)的 計算值為3，則f3,1暫時記為3.向上掃描完第1 個分支后，發(fā)現(xiàn)u3索引鏈只有1個 結(jié) 點，則f3,1=3.即 |A(u3)∩A(u1)|=3.而 |A(u3)|=3，|A(u1)|=5， 根據(jù) 式（1）得sim(A(u3),A(u1))=0.6，滿足閾值要求，輸出集合對 (u1,u3).而從u4開始，索引項的第1 個樹結(jié)點是 (u4,2,1)，沿分支向根結(jié)點方向遍歷得到 (u4,2,1;u1,5,5)的 計算值為1，則f4,1暫時記為1.向上掃描完第1 個分支后，沿著u4索引鏈找到FP-tree的下一個結(jié)點 (u4,2,1) ，同理得到 (u4,2,1;u1,5,5)的計算 值為1，則f4,1=f4,1+1=2 ， 即 |A(u4)∩A(u1)|=2.而A(u4)=2，A(u1)=5， 根 據(jù) 式（1）得sim(A(u4),A(u1))=0.4 ＜0.6 ，不輸出集合對 (u1,u4).

由于基于FP-tree 的多項集頻次計算或頻繁多項集挖掘需要遞歸建樹，運行期開銷大.為減少這一開銷，N-lists[28]采用垂直數(shù)據(jù)結(jié)構(gòu)表示FP-tree 樹結(jié)點，F(xiàn)P-tree 樹結(jié)點的構(gòu)建過程包含2 步：1）構(gòu)建一種類似FP-tree 的樹結(jié)構(gòu)-前序后序編碼樹（pre-order postorder code tree, PPC-tree）；2）構(gòu)建PPC-tree 結(jié)點列表Nlist.如圖2（b）所示，PPC-tree 基本與FP-tree 結(jié)構(gòu)相似，不同之處在于PPC-tree 不包含索引鏈，同時每個樹結(jié)點增加了標(biāo)識結(jié)點在先序樹遍歷和后序樹遍歷中位置的先序編碼和后序編碼.PPC-tree 結(jié)點旁邊括號中的數(shù)字，左邊是先序編碼，右邊是后序編碼.結(jié)合2個結(jié)點的先序編碼、后序編碼可快速判斷2 個結(jié)點之間的祖先后代關(guān)系：祖先結(jié)點的先序編碼大且后序編碼小.為此，PPC-tree 的建樹過程增加了2 次樹的遍歷：先序遍歷和后序遍歷.N-lists 是由PPC-tree中元素相同的結(jié)點按先序編碼升序排序的列表，其數(shù)據(jù)結(jié)構(gòu)包含頭表和元素的結(jié)點列表N-list.頭表結(jié)構(gòu)及內(nèi)容與圖2（a）類似，只是頭指針指向相應(yīng)元素的N-list 首地址.本文的圖2（b）中只畫出頭表中的元素信息部分.N-lists 的結(jié)點數(shù)據(jù)結(jié)構(gòu)為三元組：（計數(shù)，（先序編碼，后序編碼））.頭表元素ui的N-list 的第1個結(jié)點表項記為Ni,0， 第2 個結(jié)點表項記為Ni,1，依此類推.如u5的 第1 個結(jié)點N5,0=(2,(4,1)).特別地，頭表元素的N-list 各項計數(shù)之和為元素的單項頻次，例如，u5的 N-list 中2 項元組的計數(shù)之和為N5,0.計數(shù)+N5,1.計數(shù)=2+1=3=f5.

假定二項集 (ui,uj)都 是排序的二項集，ui的先序編碼小于uj，則 (ui,uj)的N-list 也是按先序編碼升序排序的列表，可通過將ui與uj的N-lists 按規(guī)則相交合并而成：分別取ui和uj的 N-lists 上的任意一個結(jié)點Ni,k和Nj,l,如果結(jié)點之間存在祖先后代關(guān)系，則將(Nj,l.計數(shù),(Ni,k.先序編碼,Ni,k.后序編碼)) 插 入 (ui,uj)的N-list 中.例如，u3和u5對應(yīng)的N-lists 相交合并可生成(u3,u5) 的N-list， 首 先u3的N-list 只 包 含1 個 結(jié) 點N3,0=(3,(3,2))，u5的 N-list 包含2 個三元組N5,0=(2,(4,1)),N5,1=(1,(7,5)).當(dāng) 比 較N3,0和N5,0時 ，由 于 3 ＜4且2 ＞1，N3,0是N5,0的祖先，即它們間有祖先后代關(guān)系，則向 (u3,u5) 的N-list 中插入1 個結(jié)點N(3,5),0=(N5,0.計數(shù),(N3,0.先序編碼,N3,0.后序編碼))=(2,(3,2))； 當(dāng) 比 較N3,0和N5,1時 ，由于 3 ＜7且 2 ＜5，它們之間沒有祖先后代關(guān)系，因此不必向 (u3,u5)的N-list 插入新的結(jié)點.同理，頻次fi,j的計算可以通過對 (ui,uj)的N-list 各項計數(shù)求和得到，如f3,5=2， 即 |A(u3)∩A(u5)|=2， 而 |A(u3)|=3，|A(u5)|=3， 根 據(jù) 式（1）得sim(A(u3),A(u5))=0.5，不 滿足閾值要求，不輸出集合對 (u3,u5).

基于N-lists 的多項集頻次計算是基于N-lists 進(jìn)行交叉合并的，不需要遞歸建樹，提升了計算性能，但在只計算二項頻次時轉(zhuǎn)變?yōu)? 個N-lists 的所有元素兩兩對比的計算，性能反而不理想.而面向大規(guī)模集合構(gòu)建的FP-tree 的樹結(jié)點數(shù)量多，指針結(jié)點的尋址時間長，緩存訪問命中率低，降低了遍歷樹的效率.線性前綴樹（linear prefix tree, LP-tree）[29]，在FP-tree 結(jié)構(gòu)的基礎(chǔ)上將其結(jié)點的元素字段改用數(shù)組表示，存儲多個元素信息，減少內(nèi)存使用并加快尋址.如圖2（c）所示，LP-tree 的頭表結(jié)構(gòu)及內(nèi)容與圖2 （a）完全一樣，所以本文只畫出頭表中的元素信息部分.而結(jié)點信息改為2 項內(nèi)容：一個是存儲元素信息的數(shù)組，另一個是父結(jié)點.該數(shù)組每一項的數(shù)據(jù)域用五元組表示（元素, 頻次, 計數(shù), 下一個元素相同結(jié)點的指針, 分支標(biāo)志）.其中，“下一個元素相同結(jié)點的指針”用于構(gòu)建索引鏈，指向下一個元素相同的項在另一個結(jié)點的數(shù)組中的位置.父結(jié)點指向其前綴最后一個元素所在的結(jié)點及其在數(shù)組的位置.其中，當(dāng)一個元素沒有下一個元素相同的結(jié)點時，相應(yīng)指針為 N ull.分支標(biāo)志為t時表示有大于等于2 個以上的序列片段的最長共同前綴止于該元素，f表示不存在分支.LPtree 結(jié)點結(jié)構(gòu)合并了多個元素結(jié)點的信息，減少了FPtree 樹結(jié)點數(shù)量，圖2（a）中的FP-tree 有9 個結(jié)點，而圖2（c）中的LP-tree 只有4 個結(jié)點.LP-tree 通過連續(xù)存儲元素信息提高了計算的效率，但結(jié)點內(nèi)部存在的分支、復(fù)雜的遍歷流程帶來運行期開銷.

1.2 TELP-tree 數(shù)據(jù)結(jié)構(gòu)

為進(jìn)一步提高基于FP-tree*的集合相似度自連接的計算效率，我們提出了一種遍歷效率更高的線性前綴樹TELP-tree（traversal efficient LP-tree）的數(shù)據(jù)結(jié)構(gòu).與線性前綴樹LP-tree 相似，TELP-tree 的樹結(jié)點也采用線性數(shù)組存儲多個元素信息以減少樹結(jié)點數(shù)量，提高樹的遍歷效率；而不同的是，TELP-tree 樹結(jié)點內(nèi)部沒有分支，避免結(jié)點內(nèi)分支帶來復(fù)雜的運行期遍歷流程管理，從而減少相應(yīng)的運行期開銷.

定義1.TELP-tree.TELP-tree，數(shù)據(jù)結(jié)構(gòu)包含頭表H和樹結(jié)構(gòu)，頭表H與FP-tree 一樣結(jié)構(gòu).TELP-tree 樹結(jié)點（TELP-tree node）N包含建樹和遍歷樹所需的3項內(nèi)容：父結(jié)點P、子結(jié)點C和存儲元素信息的數(shù)組E，即一個包含k個元素的Ni表示為Ni={P,C,E={E1,E2,…,Ek}}.而數(shù)組元素Ej可用三元組（元素, 頻次, 計數(shù)）表示.一個由c個樹結(jié)點組成的TELP-tree 可以表示為 {H,N1,N2,…,Nc}.

TELP-tree 的頭表與FP-tree 一樣，因此，構(gòu)建TELP-tree 頭表與構(gòu)建FP-tree 的方式是一樣的.而樹結(jié)點間存在差異，因此TELP-tree 樹結(jié)構(gòu)的構(gòu)建與FPtree, LP-tree 的構(gòu)建也存在差別.對任一序列S(ai)，與FP-tree, LP-tree 相似，始于根結(jié)點，找到TELP-tree 中與S(ai) 有 最長共同前綴的路徑P，將P相應(yīng)共同前綴上結(jié)點中所有元素的計數(shù)加1，然后將這些元素從S(ai)中移去，形成S(ai)′.如果||S(ai)′||=0，對該序列的處理完成.否則，設(shè)P上最后1 個結(jié)點中與S(ai)′有最長公共前綴的后繼結(jié)點為Nsucc，根據(jù)該公共前綴長度是否為0，樹結(jié)點的構(gòu)建和樹結(jié)點插入到樹結(jié)構(gòu)有所不同：1）長度為0 時，構(gòu)建一個新的結(jié)點，將S(ai)′中的元素依序存進(jìn)其數(shù)組中，并將該結(jié)點插入樹結(jié)構(gòu)和鏈接到對應(yīng)元素的索引鏈的末尾，這種情況與LPtree 的樹結(jié)構(gòu)構(gòu)建是一致的；2）長度不為0 時，將Nsucc所有公共前綴上的元素計數(shù)加1.然后將S(ai)′中在 公 共前 綴 上 的 元 素 移 除， 形 成S(ai)′′,如 果||S(ai)′′||=0，對該序列的處理完成，這種情況與LPtree 的樹結(jié)構(gòu)構(gòu)建是一致的.如果||S(ai)′′||=0，將構(gòu)建一個新的結(jié)點N′， 將S(ai)′′中的元素都依序存進(jìn)其數(shù)組中.同時將Nsucc中不是公共前綴的元素都移出，重構(gòu)一個新的結(jié)點N′′.最后將新構(gòu)建的結(jié)點N′和N′′插入樹中，即Nsucc是N′和N′′的父結(jié)點，并將N'和N''分別鏈接到對應(yīng)元素的索引鏈的末尾.這一步是TELPtree 與LP-tree 因為樹結(jié)點結(jié)構(gòu)不同帶來的樹結(jié)構(gòu)構(gòu)建的不同之處，結(jié)點內(nèi)部沒有分支，簡化了樹結(jié)點的同時也簡化了樹結(jié)構(gòu)的構(gòu)建.

基于圖1 數(shù)據(jù)構(gòu)建的TELP-tree 如圖2（d）所示，其中 (u1,5;u2,5)是所有輸入序列的公共前綴，基于構(gòu)建 樹 的 規(guī) 則， (u1,5)和 (u2,5)將 分 別 成 為TELP-tree 的1 個結(jié)點里的2 個數(shù)組元素.而序列(u1,5;u2,5;u3,3;u5,3;u4,2)移 去公共前綴 (u1,5;u2,5)之后的后續(xù)片段為(u3,3;u5,3;u4,2)，(u1,5;u2,5;u3,3;u5,3)移 除 公 共 前 綴(u1,5;u2,5) 后是 (u3,3;u5,3)， (u1,5;u2,5;u3,3)移除公共前 綴 (u1,5;u2,5) 后 是 (u3,3)， (u3,3;u5,3)是(u3,3;u5,3;u4,2)的子序列，而(u5,3)和(u4,2)沒有公共前綴，所以(u1,5), (u2,5), (u3,3)這3 個數(shù)組元素組成1 個結(jié)點，計數(shù)值分別是3, 2, 1，且結(jié)點內(nèi)部沒有分支.最終構(gòu)建的TELP-tree 有5 個結(jié)點.

相 比圖2（a）中9 個 結(jié) 點 的FP-tree，圖2（d）中5個結(jié)點的TELP-tree 結(jié)點少4 個，結(jié)點內(nèi)數(shù)組元素尋址快.相比圖2（c）的4 個結(jié)點的LP-tree，TELP-tree 的結(jié)點多了1 個，但結(jié)點數(shù)組中存儲的信息少，且前綴所在結(jié)點直接指向后續(xù)片段所在結(jié)點，避免了結(jié)點內(nèi)部分支，簡化并加速樹的遍歷.

1.3 TELP-SJ 算法

1.1 節(jié)描述了簡單的基于FP-tree*的集合相似度自連接計算流程，但該計算過程沒有采用過濾-驗證框架.為進(jìn)一步提高基于FP-tree*的集合相似度自連接計算效率，本節(jié)設(shè)計基于過濾-驗證框架和TELPtree 的集合相似度自連接算法TELP-SJ.

TELP-SJ 使用長度過濾策略來設(shè)計其過濾算法.長度過濾策略被應(yīng)用于多個集合相似度自連接算法中，如FS-Join.當(dāng)集合相似度函數(shù)為Jaccard（）時，長度過濾策略如定理1[19]所示.

定理1.給定2 個集合A和B,|A|＜|B|， 閾值t，如果|A|＜t×|B|， 那么sim(A,B)＜t.

文獻(xiàn)[19]給出定理1 的數(shù)學(xué)證明，基于定理1，2個相似的集合應(yīng)有相似的大小，反之，集合大小不相似的集合對的相似度低.與集合A的相似度大于等于t的所有集合，其集合大小一定小于等于 |A|/t.因此，可提前過濾集合大小大于 |A|/t的集合.根據(jù)1.1 節(jié)和1.2 節(jié)的建樹過程可知，序列的長度將影響樹的深度，長度越大，深度越深，樹的遍歷代價就越高.為減小構(gòu)建的樹的規(guī)模，根據(jù)定理1，我們首先設(shè)計面向構(gòu)建樹的過濾算法，該算法檢測、發(fā)現(xiàn)并刪除序列中不會與其他集合形成相似度高于閾值的集合對的集合.給定至少有2 個元組的序列S(ai)，在將它插入到TELP-tree 時前先應(yīng)用算法1 描述的面向構(gòu)建樹的過濾算法對其進(jìn)行預(yù)處理：從右向左掃描S(ai)中的元素，假設(shè)最右邊的2 個相鄰元素分別是uk和uj,如果|A(uk)|＞t×|A(uj)|， 將S(ai)按照2.2 節(jié)描述的建樹過程插入TELP-tree.如果 |A(uk)|＜t×|A(uj)|，根據(jù)定理1，我們有sim(A(uk),A(uj))＜t，即uk與uj的相似度低于閾值t.序列片段按元素頻次降序排列，此時，uk對應(yīng)的元組 (uk,A(uk)) 將 從序列S(ai)中刪除.刪除后如果|S(ai)|≤ 1，意味著ai對應(yīng)原序列中所有元素相似度都低于閾值t，原序列被舍棄，否則繼續(xù)如上述過程迭代處理S(ai).面向構(gòu)建樹的過濾算法如算法1 所示.函數(shù)getrightmost(S(ai))表 示獲取S(ai)的最右邊元素.

算法1.面向構(gòu)建樹的過濾算法.

輸入：序列S(ai)；

輸出：過濾后序列S′(ai).

①S′(ai)←S(ai)；

② while |S′(ai)|＞1 do

③ (uk,A(uk))←getrightmost(S′(ai))；

④S′′(ai)←S′(ai)-(uk,A(uk))；

⑤ (uj,A(uj))←getrightmost(S′′(ai))；

⑥ if |A(uk)|≥t×||A(uj)||

⑦ break；

⑧ else

⑨S′(ai)←S′′(ai)；

⑩ end if

? end while

? returnS′(ai).

例如，針對圖1 的示例數(shù)據(jù)，S(a5)=(u1,5;u2,5;u5,3;u6,1)， 從右向左掃描S(a5)， 最右邊的 |A(u6)|=1，而過濾算法根據(jù)構(gòu)建樹（算法1），構(gòu)建樹的過程就是逐步插入樹節(jié)點的過程 |A(u5)|=3， 1/3 ＜0.6，根據(jù)面向構(gòu)建樹的過濾算法刪除元組 (u6,1)， 得到S′(a5)=(u1,5;u2,5;u5,3).此時最右邊的|A(u5)|=3， 而|A(u2)|=5，3/5=0.6 ，將S′(a5)插入到 TELP-tree.應(yīng)用面向構(gòu)建樹的過濾算法構(gòu)建的TELP-tree 如圖3 所示，與圖2（d）中沒有應(yīng)用該過濾算法構(gòu)建的TELP-tree 相比，圖3中的TELP-tree 減少了1 個樹結(jié)點N4， 樹的結(jié)點N3的數(shù)組元素減少了1 個，頭表元素 |H|也減少了1 個，即少了u6相應(yīng)的信息.

Fig.3 A TELP-tree is constructed based on filtering algorithm圖3 基于過濾算法構(gòu)建的TELP-tree

構(gòu)建好TELP-tree 后，通過沿著頭表結(jié)點索引鏈遍歷樹并統(tǒng)計所有以這些結(jié)點為后綴的二項集頻次，根據(jù)樹的特征，樹結(jié)點元素頻次越高越靠近根結(jié)點.樹結(jié)點內(nèi)數(shù)組元素按頻次倒序排序.樹的遍歷代價跟遍歷的結(jié)點數(shù)和結(jié)點內(nèi)數(shù)據(jù)元素的個數(shù)有關(guān).沿著索引鏈從遠(yuǎn)離根結(jié)點的樹結(jié)點向著根結(jié)點的方向遍歷樹，統(tǒng)計索引鏈結(jié)點元素與其他元素的二項頻次.同樣，根據(jù)定理1，非根結(jié)點元素ui及其祖先結(jié)點元 素uj如 果 滿 足 |A(ui)|＜t×|A(uj)|， 可 得sim(A(ui),A(uj))＜t，即這2 個元素相似度低于閾值，此時，可以停止沿著這條分支向著根結(jié)點方向統(tǒng)計，即過濾對應(yīng)的集合對以減少遍歷.面向遍歷樹的過濾算法見算法2，其中，Ancestor(N)表 示樹中N的祖先結(jié)點；N.x中 的“.” 表示 取結(jié)點N的 相應(yīng)數(shù) 據(jù)域x， 如N.E[l]表示取結(jié)點N的元素數(shù)組E的第l個元素.

算法2.面向遍歷樹的過濾算法.

輸入：元素ui, 樹結(jié)點N, 頻次統(tǒng)計f；

輸出：頻次統(tǒng)計f.

① whileN不為根結(jié)點 do

②l←|N.E|-1；

③ whilel≥0 do

④ if|A(ui)|＜t×|A(N.E[l])|

⑤ goto ?；

⑥ else

⑦fi,N.E[l]+=N.E[l].計數(shù)

⑧ endif

⑨ end while

⑩N←Ancestor(N)；

? end while

? returnf.

基于面向構(gòu)建樹的過濾算法構(gòu)建TELP-tree，按規(guī)則遍歷樹并計算集合相似度自連接：1）遍歷頭表H中所有元素ui， 并初始化f；2）通過ui的索引鏈，遍歷其所有樹結(jié)點，對每個樹結(jié)點調(diào)用面向遍歷樹的過濾算法，并更新f；3）根據(jù)f計算出集合相似性，并輸出相似性大于閾值的集合對.例如從圖3 的頭表的(u4,2)開 始，順著索引項第1 個樹結(jié)點N2的數(shù)組元素(u4,2,1) 開始統(tǒng)計包含u4的二項集的頻次.如(u4,2,1;u5,3,2)的 二項計數(shù)值較小者為1，則f4,5=0+1=1.同時注意到 |A(u4)|=2， |A(u2)|=5， 2 ＜0.6×5，因此，針對 (u4,2,1) ，從N2向著根結(jié)點的方向遍歷樹時，只需要遍歷N2的 元素信息數(shù)組，不需要遍歷N1.因此f4,5=1， 即|A(u4)∩A(u5)|=1.而|A(u4)|=2，|A(u5)|=3，根據(jù)式（1）得sim(A(u4),A(u5))=0.25 ＜0.6，不輸出集合對 (u4,u5).圖2 和圖3 中灰色框的元素表示統(tǒng)計包含u4的二項集頻次時要遍歷的元素，沒有填充灰色的框的結(jié)點和數(shù)組元素表示沒有遍歷的點或元素.由此，針對TELP-tree，統(tǒng)計包含u4的二項集的頻次要遍歷的結(jié)點數(shù)和數(shù)組元素分別是1 和2，而在使用過濾算法的情況下，要遍歷的結(jié)點數(shù)和數(shù)組元素的分別是3 和6，遍歷次數(shù)大大減少，提高了遍歷效率.

以上面向構(gòu)建樹和樹遍歷的2 個過濾算法同樣可以使用于其他基于FP-tree*的集合相似度自連接算法.綜上，TELP-SJ 的算法的偽代碼見算法3.基于FP-tree 的集合相似度自連接算法FP-SJ、基于LP-tree的 LP-SJ 均與 TELP-SJ 的計算思路基本一致，不同之處在于算法3 中行?，即：如果是FP-SJ，則構(gòu)建FPtree；如果是LP-SJ，則構(gòu)建LP-tree.遍歷樹的一些細(xì)節(jié)有稍許區(qū)別，如Ancestor(nk)的實現(xiàn)和結(jié)點的定位等操作，這里不贅述.而基于N-lists 的集合相似度自連接算法PPC-SJ，則是構(gòu)建PPC-tree 后，構(gòu)造N-lists，然后對任意2 個N-lists 的所有元素兩兩對比驗證完成 計 算.FP-SJ，LP-SJ， TELP-SJ，PPC-SJ 這4 種 基 于FP-tree*的集合相似度自連接算法統(tǒng)稱為FP-tree*-SJ.

算法3.TELP-SJ 算法.

輸入：數(shù)據(jù)集D={〈ui,{ai1,ai2,…,aik}〉} ， 閾值t；

輸出：滿足閾值的集合對集合P.

①U←?，S←?，S′←?，P←?；

② for eachui，A(ui)inD

③ for eachaij∈A(ui)

④U(ai j)←U(aij)+(ui:|A(ui)|)；

⑤ end for

⑥ end for

⑦ forU(ai) inU

⑧ 對U(ai)按 頻次降序排序得到S(ai)；

⑨ 對S(ai) 調(diào) 用算法1 得到S′(ai)；

⑩ end for

? 根據(jù)S′建樹tree；

? for eachui∈tree.H

? 初始化頻次f；

? for eachNkinui的索引鏈

? 對ui，Nk，f調(diào)用算法2；

? end for

? 根據(jù)f計算出sim(ui,uj)；

?P←P+{(ui,uj)s.t.sim(ui,uj)＞t}；

? end for

? returnP.

2 基于MapReduce 的集合相似度自連接算法FastTELP-SJ

MapReduce 是一種高效的并行分布式集群計算框架.一個MapReduce 任務(wù)的運行主要包含2 個階段：映射（Map）階段和規(guī)約（Reduce）階段.Map 階段首先將存儲在分布式文件系統(tǒng)HDFS 上的輸入數(shù)據(jù)劃分為多個分片；然后就近分發(fā)至集群多個計算節(jié)點獨立并行運行函數(shù)map，處理數(shù)據(jù)并以〈Key,Value〉對的形式輸出中間結(jié)果.之后中間結(jié)果按照Key值進(jìn)行合并（combine）、重新分配（shuffle）、排序（sort）后再分發(fā)至1 個或多個節(jié)點進(jìn)行Reduce 階段運算，獨立并行運行函數(shù)reduce進(jìn)行匯總.最終各個函數(shù)reduce的結(jié)果仍以〈Key,Value〉對的方式輸出并保存在HDFS 上.

第1 節(jié)設(shè)計了系列基于FP-tree 及其擴展結(jié)構(gòu)的集合相似度自連接算法FP-tree*-SJ，這些算法的特征是建樹后，整棵樹需要保留在內(nèi)存中進(jìn)行計算，當(dāng)集合規(guī)模增大時，樹的規(guī)模增大，對內(nèi)存的要求增大，樹的遍歷計算代價也增大.為進(jìn)一步提高計算性能，本節(jié)設(shè)計基于TELP-tree 和MapReduce 的集合相似度自連接算法FastTELP-SJ.圖4 展示了FastTELP-SJ 的計算過程.FastTELP-SJ 包含2 個MapReduce 任務(wù)，分別完成數(shù)據(jù)集轉(zhuǎn)置、建樹和集合相似度自連接的計算.1.3 節(jié)設(shè)計的2 階段過濾算法，分別應(yīng)用于任務(wù)1和任務(wù)2.

Fig.4 An illustration of the computation process of the parallel and distributed set similarity self-join of FastTELP-SJ with MapReduce圖4 基于MapReduce 的并行分布式集合相似度自連接FastTELP-SJ 的計算流程示意圖

2.1 轉(zhuǎn)置數(shù)據(jù)集

任務(wù)1 的函數(shù)map計算每個ui的 頻次 |A(ui)|、輸出〈Key=aid,Value=(ui:|A(ui)|)〉對, 實現(xiàn)了原數(shù)據(jù)集的轉(zhuǎn)置.與Key值 相同的Value將被合并和發(fā)送到同一個函數(shù)reduce.任一應(yīng)用ai的Value集合標(biāo)記為U(ai).函數(shù)reduce 將U(ai)元素按照頻次降序排序得到序列S(ai)， 調(diào)用算法1 得到S′(ai)， 輸出鍵值對〈Key=ai,Value=S′(ai)〉.例如，圖4 任務(wù)1 的Reduce 階段中S(a5)=(u1,5;u2,5;u5,3;u6,1) , 函數(shù)reduce對S(a5)應(yīng)用算法1，從右向左掃描S(a5)， 最右邊的 |A(u6)|=1， 而 |A(u5)|=3，1/3 ＜0.6 ，刪 除 數(shù) 據(jù) (u6,1).同 時 |A(u2)|=5， 3/5 ≥0.6，因此輸出結(jié)果〈a5,(u1,5;u2,5;u5,3)〉.任務(wù)1 的函數(shù)map與reduce的功能分別與算法3 中行②～⑥和行⑦～⑩類似，故不再贅述.

當(dāng)所有reduce函數(shù)完成計算后，節(jié)點master將啟動一個獨立進(jìn)程對元素分組，按照頻次將元素排序，函數(shù)seq(ui)表 示ui的序號.假設(shè)gNum表 示組數(shù)，gi表示ui的組標(biāo)識號gid.基于FP-tree 樹的并行分布式計算有多種分組策略[30]，這里采用基于均衡預(yù)估遍歷負(fù)載的策略，即gi=seq(ui)modgNum.

2.2 構(gòu)建樹并計算集合相似度自連接

FastTELP-SJ 采用集合數(shù)據(jù)分段過濾與驗證的設(shè)計思路，為此，任務(wù)2 首先切分序列，按分段劃分?jǐn)?shù)據(jù)集，然后根據(jù)數(shù)據(jù)集分片并行獨立構(gòu)建TELP-tree計算集合相似度自連接.其中函數(shù)map完成數(shù)據(jù)集劃分工作.對任一S(ai)，函數(shù)map的工作流程為：1）根據(jù)S(ai) 最 右邊元素gid輸出鍵值對〈Key=gid,Value=S(ai)〉 ；2）從右向左遍歷S(ai)中 的元素uk， 如果與gid即gk相 等的鍵值對已輸出，則將該uk從S(ai)中刪去；如果S(ai)不為空，跳回1）繼續(xù)迭代執(zhí)行.例如，圖4任務(wù)2 的函數(shù)map對序列S(a5)=(u1,5;u2,5;u5,3)將輸出2 個結(jié)果：〈 1,(u1,5;u2,5)〉 和〈0,(u1,5;u2,5;u5,3)〉.任務(wù)2 中切分序列的偽代碼如算法4 所示.

算法4.序列切分算法.

輸入：已排序序列S(ai) ， 元素分組gid；

輸出：劃分結(jié)果R=〈{gid,S〉}.

①R←?,G←?；

② while|S(ai)|＞0

③(uik,|A(uik)|)←getrightmost(S(ai))；

④ifgik∈G

⑤R←R∪{〈gik,S(ai)〉}；

⑥G←G∪{gik}；

⑦ end if

⑧S(ai)←S(ai)-(uik,|A(uik)|)；

⑨ end while

⑩ returnR.

所有Key即gid相同的序列片段將被分配給同一個節(jié)點的函數(shù)reduce.因為集合相似度自連接僅需要計算單項頻次和二項頻次，結(jié)合面向MapReduce 計算而設(shè)計的精簡FP-tree（reduced FP-tree）[29]的結(jié)構(gòu)特征，函數(shù)reduce在構(gòu)建TELP-tree 時，僅為gid與Key值相同的元素構(gòu)建頭表和索引鏈，減少內(nèi)存空間并減少建樹時間，相應(yīng)的TELP-tree 稱為精簡TELP-tree.除此之外，樹的構(gòu)建過程與1.2 節(jié)相同.

構(gòu)建好精簡TELP-tree 后，通過對頭表結(jié)點索引鏈應(yīng)用面向遍歷樹的過濾規(guī)則遍歷樹，并統(tǒng)計所有以這些結(jié)點為后綴的二項集出現(xiàn)頻次.其中樹遍歷過程與1.3 節(jié)描述的相同，而二項集頻次統(tǒng)計僅對gid與reduce的Key值相同的結(jié)點進(jìn)行統(tǒng)計.任務(wù)2 的函數(shù)reduce與算法4 的行?～?類似，故不再贅述.

綜上，F(xiàn)astTELP-SJ 算法的計算流程示例見圖4.其他FP-tree*-SJ 的MapReduce 計算可采用類似的設(shè)計，相應(yīng)地，基于MapReduce 的FP-tree*-SJ 算法被命名為FastFP-tree*-SJ.

3 性能評估

基于FP-tree*的算法通過將數(shù)據(jù)壓縮在內(nèi)存中進(jìn)行計算，減少I/O 操作，減小候選集，提高驗證兩兩集合相似度是否大于閾值的運行效率.但這些算法也增加了動態(tài)構(gòu)建樹等運行期開銷，同時，整棵樹需被保留在內(nèi)存中進(jìn)行計算，對內(nèi)存需求比較大.我們將從運行時間、內(nèi)存占用率、磁盤使用量這3 類指標(biāo)通過3 組比較實驗評估FastTELP-SJ 算法的性能：1）TELP-SJ 算法與基于其他FP-tree*-SJ 算法的比較；2）FastTELP-SJ 算法與TELP-SJ 算法的比較；3）FastTELPSJ 與現(xiàn)有經(jīng)典算法的比較.

Apache Hadoop[31]和 Apache Spark[32]是2 個最知名和最廣泛使用的MapReduce 編程模型的開源實現(xiàn).兩者最大的區(qū)別是：Apache Hadoop 的中間計算結(jié)果保存在Apache Hadoop 分布式文件系統(tǒng)中，而Apache Spark 可將中間數(shù)據(jù)結(jié)果緩存在內(nèi)存中.因此，對多次數(shù)據(jù)依賴的迭代算法、多數(shù)據(jù)依賴的計算任務(wù)，使用Apache Spark 可以減少I/O 從而提高運行效率.從第2 節(jié)的描述可見，集合相似度自連接計算不包含多次數(shù)據(jù)依賴的迭代計算.另外，還有些特定面向多核或眾核優(yōu)化的MapReduce 實現(xiàn)，如Phoenix[33], Mars[34]等.考慮到現(xiàn)有經(jīng)典算法都是基于Apache Hadoop 實現(xiàn)，因此，本文的對比實驗首先在Apache Hadoop 上復(fù)現(xiàn)經(jīng)典算法，然后實現(xiàn)本文設(shè)計的算法.

實驗使用一個包含17 個曙光TC4600 刀片節(jié)點搭建的Apache Hadoop 集群，其中1 個作為主節(jié)點，其他作為從節(jié)點.每個刀片都有2 個10 核的Intel?Xeon?E5-2 680 v2 2.8 GHz 的處理器、2 個1 TB 的磁盤、64 GB 的內(nèi)存和1 Gbps 的以太網(wǎng).刀片上安裝CentOS 6.5 操 作 系 統(tǒng)， OpenJDK 1.8.0 和 Apache Hadoop 2.7.1.相關(guān)Apache Hadoop 參數(shù)配置見表1，其他均采用缺省配置.

Table 1 Apache Hadoop Parameter Configuration表1 Apache Hadoop 參數(shù)配置

實驗數(shù)據(jù)來自4 組真實的應(yīng)用數(shù)據(jù)集：Facebook應(yīng)用數(shù)據(jù)集 II（簡記為facebook）[35]、匈牙利在線新聞門戶點擊流數(shù)據(jù)集kosarak[36]、2015 年Enron 電子郵件數(shù)據(jù)集Enron[37]和交通事故數(shù)據(jù)集accidents[38].我們將從各組數(shù)據(jù)集中提取一定量的數(shù)據(jù)分別進(jìn)行實驗，相應(yīng)數(shù)據(jù)子集命名為數(shù)據(jù)集名稱后加提取的數(shù)量，如從facebook 數(shù)據(jù)集中提取10 萬條數(shù)據(jù)，記為facebook10w.4 組數(shù)據(jù)集為各取近30 萬條數(shù)據(jù)組成的子集，其相應(yīng)數(shù)據(jù)特征總結(jié)在表2 中，其中，子集x′={x′1,x′2,…,x′n′}， 子集大小即 |x′|=n′為數(shù)據(jù)子集元素總數(shù)，表示數(shù)據(jù)集所有元素屬性合集，X(a′i)表 示擁有屬性a′i的元素，表示擁有該屬性的元素的最大個數(shù)表示所有屬性元素的平均個數(shù)，表示元素?fù)碛袑傩缘淖畲髠€數(shù)，表示元素?fù)碛袑傩缘钠骄鶄€數(shù)，表示元素?fù)碛袑傩詡€數(shù)的方差.每次計算都將運行3 次，采用平均運行時間、內(nèi)存占用率峰值和磁盤使用量用于展示實驗結(jié)果和分析.

Table 2 Characteristics of Experimental Datasets表2 實驗數(shù)據(jù)集特征

3.1 TELP-SJ 與基于其他FP-tree＊-SJ 的比較

本文分別實現(xiàn)FP-SJ, PPC-SJ, LP-SJ, TELP-SJ 這4 種基于 FP-tree 及其派生結(jié)構(gòu)的集合相似度自連接算法，并將這些算法分別運行在facebook30w,kosarak30w, Enron30w, accidents30w 這4 組數(shù)據(jù)上，閾值t的取值范圍為 0.6 ～0.9.基于FP-tree*-SJ 的集合相似度自連接計算沒有產(chǎn)生中間結(jié)果，最后輸出結(jié)果是一樣的，因此這4 種算法的磁盤使用量沒有差異.這4 組算法的區(qū)別在于樹結(jié)構(gòu)的差異及因此帶來的建樹和遍歷樹流程的差異，我們將比較這4 種算法的運行時間和內(nèi)存占用率峰值.

1） 運行時間

根據(jù)第1 節(jié)的描述，基于FP-tree*的集合相似度計算的第1 步是轉(zhuǎn)置數(shù)據(jù)集.數(shù)據(jù)子集x′轉(zhuǎn)置后的數(shù)據(jù) 集x′′的 大 小 |x′′|為x′所 有 元 素 屬 性 合 集 大 小 |A(x′)|，即|x′′|=|A(x′)|.FP-SJ, LP-SJ, TELP-SJ 等算法的計算復(fù)雜度即樹遍歷的復(fù)雜度而對PPC-SJ來說，基于構(gòu)建好N-lists的集合相似度自連接計算是對任意2個N-lists的比較，其計算復(fù)雜度O(Nlists)=|x′|×|A(x′)|2.

圖5 展示4 種FP-tree*-SJ 算法的運行時間隨著閾值t提高的變化，我們可以看到在facebook30w,Enron30w, kosarak30w 這3 組數(shù)據(jù)集上FP-SJ, LP-SJ,TELP-SJ 的運行時間比PPC-SJ 的運行時間少很多.如表2 所示，這3 組數(shù)據(jù)的 |A(x′)|很大，說明原數(shù)據(jù)子集元素屬性合集很大，即是高維大數(shù)據(jù).該實驗數(shù)據(jù)說明這3 種算法比PPC-SJ 更適合處理高維大規(guī)模集合相似度自連接計算，其中TELP-SJ 的運行時間最少.

Fig.5 Relationship between FP-tree*-SJ’s running time and the threshold圖5 FP-tree*-SJ 的運行時間與閾值關(guān)系

在accidents30w 數(shù)據(jù)集上PPC-SJ 的運行效率最好，其次是TELP-SJ, 最差是FP-SJ.accidents30w 的|A(x′)|=458， 而其 他3 組的都很大，所以PPC-SJ 的運行效率最好.該實驗數(shù)據(jù)說明PPC-SJ 比其他3 種算法適合處理低維大規(guī)模集合相似度自連接計算.此種情況下，TELP-SJ 比FP-SJ, LP-SJ 的運行效率也要高.

表3 展示了閾值t= 0.6 時4 種FP-tree*-SJ 算法處理Enron30w 數(shù)據(jù)集時各分步的運行時間，包括建樹時間、遍歷樹時間、總耗時.表4 展示了TELP- SJ與其他3 種算法的相對性能提升率.由表3 和表4 可見，4 種算法遍歷樹的時間在總耗時中占比較高，而TELP-SJ 和LP-SJ 的遍歷時間少于FP-SJ 和PPC-SJ，這與第1 節(jié)的分析一致.其中，TELP-SJ 的遍歷時間最少，相比于FP-SJ 和PPC-SJ 性能分別提高了32%和83%.同時，我們也看到，TELP-SJ 的建樹時間和遍歷樹時間都比LP-SJ 少，其中建樹時間性能提高了45%，遍歷時間性能提高了17%，這也與第1 節(jié)的分析一致.隨著閾值t的增大，因為大部分?jǐn)?shù)據(jù)在第1階段過濾中被過濾掉，候選集規(guī)模小，建樹和遍歷樹的代價差異減小，相應(yīng)地TELP-SJ 與FP-SJ 和 LP-SJ的運行時間差異減小.

Table 3 Detailed Execution Time of Enron30w Dataset handled by FP-tree＊-SJ表3 FP-tree＊-SJ處理Enron30w數(shù)據(jù)集的細(xì)分運行時間 s

Table 4 Relative Performance Improvement of TELP-SJ Compared with Other FP-tree＊-SJ表4 TELP-SJ 相對于其他FP-tree＊-SJ 的性能提升 %

我們以Enron 數(shù)據(jù)集為例，閾值t=0.6，從5 萬條數(shù)據(jù)起，每次每組增加5 萬條，共6 組數(shù)據(jù)，分別運行4 種算法以觀察它們的運行時間與數(shù)據(jù)子集大小的關(guān)系.如圖6 所示，隨著數(shù)據(jù)子集大小的增加，TELP-SJ 的運行時間增長速度低于另外3 種算法，可擴展性最好.

Fig.6 Relationship between FP-tree*-SJ’s running time and the size of Enron’s sub-datasets圖6 FP-tree*-SJ 的運行時間與Enron 數(shù)據(jù)子集大小的關(guān)系

2） 內(nèi)存占用峰值

圖7 展示了闕值t= 0.6 時4 種算法運行期的內(nèi)存占用率.由圖7（a）（b）可見，4 種FP-tree*-SJ 算法運行期在facebook30w 和kosarak30w 數(shù)據(jù)子集上的內(nèi)存占用率峰值相近，圖7（c）（d）則顯示在Enron30w和acciden30w 數(shù)據(jù)集上，F(xiàn)P-SJ 的內(nèi)存占用率峰值最高，PPC-SJ 相對較低和TELP-SJ 最低，這說明TELPSJ 使用數(shù)組存儲了更多的元素，具有較好的壓縮比，而PPC-tree 因為使用N-lists 進(jìn)行計算，不需要建立相同元素結(jié)點間的索引鏈，減少了內(nèi)存開銷.

Fig.7 Memory usage of FP-tree*-SJ (t = 0.6)圖7 FP-tree*-SJ 的內(nèi)存占用率（t = 0.6）

3.2 FastTELP-SJ 算法與TELP-SJ 算法的比較

本節(jié)我們以TELP-tree 為例，以FastTELP-SJ 相對TELP-SJ 的運行時間加速比及內(nèi)存占用峰值評估MapReduce 對基于FP-tree*的集合相似度自連接算法的加速效果.

實驗將FastTELP-SJ 和TELP-SJ 分別運行在4 個數(shù)據(jù)集的子集上，圖8 描繪了2 種算法的相對加速比.其中數(shù)據(jù)子集大小始于5 萬條，每次每組增加5萬條，共6 組數(shù)據(jù)，閾值t分別設(shè)置為0.6 和0.9.由圖8 可見，當(dāng)閾值t= 0.6 時，隨著數(shù)據(jù)子集大小的增加，相對加速比加大.FastTELP-SJ 相對于TELP-SJ 的相對加速比在accidents 數(shù)據(jù)子集上高達(dá)10，且在facebook 和Enron 數(shù)據(jù)子集上相對加速比的增長近似于線性.當(dāng)閾值t= 0.9 時，當(dāng)數(shù)據(jù)子集大小等于3 萬條時，相對加速比在Enron 和accidents 數(shù)據(jù)子集上分別約為2 和7，可見采用并行分布式計算框架MapReduce 可加速基于FP-tree*的集合相似度自連接計算.

Fig.8 Relative speedup of FastTELP-SJ and TELP-SJ圖8 FastTELP-SJ 與TELP-SJ 的相對加速比

當(dāng)數(shù)據(jù)子集比較小時，如圖8 中數(shù)據(jù)集大小小于15 萬條時，F(xiàn)astTELP-SJ 和TELP-SJ 算法的相對加速比在facebook, kosarak, Enron 等數(shù)據(jù)子集上都小于1.同時，在所有kosarak 數(shù)據(jù)子集上的相對加速比增長都緩慢，且小于1.5.這是因為該數(shù)據(jù)集的 |A(x′)|和(|X(a′i)|)偏低，如圖9 所示，轉(zhuǎn)置后數(shù)據(jù)子集的規(guī)模和維度都不大，相當(dāng)于小數(shù)據(jù)集.同理，當(dāng)閾值t=0.9 時，大部分?jǐn)?shù)據(jù)在第1 階段過濾中被過濾掉，規(guī)模減小后的候選集變成了小數(shù)據(jù)集，因此，2 種算法的相對加速比在facebook 和kosarak 數(shù)據(jù)子集中都小于1.這是因為基于并行分布式計算框架MapReduce 的計算有額外的運行期開銷，包括數(shù)據(jù)劃分、合并、重新分配、排序等，當(dāng)數(shù)據(jù)集比較小時，額外地運行其開銷抵消甚至超過降低切分?jǐn)?shù)據(jù)并行計算帶來的提升.此時，TELP-SJ 比FastTELP-SJ 的運行效率高.

Fig.9 Relationship between relative speedups of FastTELP-SJ and TELP-SJ, and the threshold圖9 FastTELP-SJ 和TELP-SJ 的相對加速比與閾值的關(guān)系

另外，圖9 描繪了2 種算法的相對加速比與閾值t的關(guān)系.數(shù)據(jù)子集大小均為30 萬條，閾值t設(shè)置為 0.6 ～0.9.從圖9 可以看出FastTELP-SJ 和TELP-SJ的相對加速比在4 個數(shù)據(jù)集上都大于1，且隨著閾值的減小，相對加速比在不斷增大.這是因為在閾值減小時，第1 階段過濾后得到的候選集規(guī)模變大，需要進(jìn)行兩兩交集大小計算的集合對個數(shù)增多，利用并行分布式計算框架MapReduce 的FastTELP-SJ 能使用更多計算資源完成計算，因而減小計算耗時.

圖10 描 繪 的 是 闕 值t=0.6時FastTELP-SJ 和TELP-SJ 在4 個數(shù)據(jù)子集上的運行期內(nèi)存占用率，從圖10 可見，除了在enron30w 數(shù)據(jù)子集上兩者的內(nèi)存占用率峰值基本相等外，在其他3 個子集上FastTELP-SJ的內(nèi)存占用率峰值接近于TELP-SJ 的 1/2，即采用并行分布式計算框架MapReduce 可減少單個節(jié)點的內(nèi)存負(fù)載.

Fig.10 Memory usage of FastTELP-SJ and TELP-SJ (t = 0.6)圖10 FastTELP-SJ 與TELP-SJ 的內(nèi)存占用率（t = 0.6）

3.3 FastTELP-SJ 與現(xiàn)有經(jīng)典算法的比較

從3.1 節(jié)和3.2 節(jié)的實驗結(jié)果可見，F(xiàn)astTELP-SJ在處理大規(guī)模集合相似度自連接計算時相較于基于其他FP-tree*-SJ 算法運行效率最高.RP-PPJoin 和FSJoin 是基于MapReduce 的集合相似度自連接算法的代表.另外，最近提出的位圖過濾[12]在單機和GPU系統(tǒng)上運行均展現(xiàn)了它的有效性.在本節(jié)，為了更全面地評估FastTELP-SJ 的性能，本文同時設(shè)計并實現(xiàn)基于位圖過濾策略的RP-PPJoin，記為RP-PPJoin +Bitmap.我們將通過FastTELP-SJ 與RP-PPJoin, RPPPJoin + Bitmap, FS-Join 這4 種算法的比較實驗評估FastTELP-SJ 的性能.

1） 運行時間

首先將這4 種算法運行在facebookb30w, kosarak 30w, Enron30w, accidents30w 這4 組 數(shù) 據(jù) 集 上.閾 值t的取值范圍為 0.6 ～0.9.圖11 展示4 種算法隨著閾值t的提高運行時間的變化，可以看到通過使用位圖過濾，RP-PPJoin + Bitmap 在facebookb30w, kosarak30w,Enron30w 上的運行效率都得到提高.而FastTELP-SJ的運行時間在這3 個數(shù)據(jù)集上都優(yōu)于其他3 種算法，尤其在閾值t＜0.7 時運行時間明顯降低很多.這主要是TELP-SJ 將數(shù)據(jù)壓縮在內(nèi)存中進(jìn)行計算，減少了I/O 次數(shù)，減小了候選集和降低了計算復(fù)雜度.而此時RP-PPJoin, RP-PPJoin + Bitmap, FS-join 算法產(chǎn)生較大候選集，其O(kn2)的高復(fù)雜度驗證計算延長了運行時間.尤其對accidents30w，當(dāng)t≤0.85時，F(xiàn)S-Join 無法在當(dāng)前計算環(huán)境中完成計算，當(dāng)t＜0.7時，RP-PPJoin和RP-PPJoin+Bitmap 的運行時間大幅度升高，而FastTELP-SJ 的運行時間增長不多，運行效率最高.

Fig.11 Relationship between running time of FastTELP-SJ, RP-PPJoin, RP-PPJoin+Bitmap and FS-Join, and the threshold圖11 FastTELP-SJ 和RP-PPJoin, RP-PPJoin+Bitmap, FS-Join 的運行時間與閾值的關(guān)系

圖12 描繪了這4 種算法的運行時間與數(shù)據(jù)子集大小的關(guān)系，以accidents 數(shù)據(jù)集為例，閾值t分別設(shè)置為0.6 和0.9.其中，0.6 代表了低閾值情況，而0.9代表了較高閾值的情況.數(shù)據(jù)子集大小始于5 萬條、每次每組增加5 萬條，取6 組數(shù)據(jù)，分別運行這4 種算法并觀察它們的運行時間與數(shù)據(jù)子集大小的關(guān)系.如圖12（a）所示，當(dāng)t=0.6時，F(xiàn)astTELP- SJ 的運行時間低于另外3 種算法，且其運行時間隨數(shù)據(jù)增長呈線性增長，可擴展性優(yōu)于另外3 種算法.當(dāng)t=0.9時，高閾值下各算法應(yīng)用過濾策略過濾了大量相似度低于閾值的候選集合對.此時，F(xiàn)astTELP-SJ 的運行期開銷如建樹時間等導(dǎo)致它的總運行時間高于RPPPJoin 和RP-PPJoin + Bitmap，但仍然低于FS-Join，如圖12（b）所示，這個結(jié)果也與圖10 中t值較大時的結(jié)果一致.

Fig.12 Relationship between running time of FastTELP-SJ,RP-PPJoin, RP-PPJoin+Bitmap and FS-Join, and the size of accidents’ sub-datasets圖12 FastTELP-SJ, RP-PPJoin, RP-PPJoin + Bitmap,FS-Join 的運行時間與accidents 數(shù)據(jù)子集大小的關(guān)系

最后，我們評估這4 種算法的運行時間與集群規(guī)模的關(guān)系，其中，集群規(guī)模為集群節(jié)點個數(shù).實驗以facebook30w 數(shù)據(jù)集為例，閾值t設(shè)置為0.6，集群規(guī)模起始計算節(jié)點為2，依次增加2 個直至16 個，分別運行4 種算法并觀察它們的運行時間與集群規(guī)模的關(guān)系.圖13 描繪了實驗結(jié)果，隨著集群節(jié)點個數(shù)的增加，相比于RP-PPJoin, RP-PPJoin+Bitmap, FSJoin 和FastTELPSJ 運行時間的變化速率下降得更慢.這說明相較于其他3 種算法，F(xiàn)astTELP-SJ 的擴展性最好.

Fig.13 Relationship between running time of FastTELP-SJ,RP-PPJoin, RP-PPJoin+Bitmap and FS-Join, and the cluster’s size圖13 FastTELP-SJ, RP-PPJoin, RP-PPJoin + Bitmap, FSJoin 的運行時間與集群規(guī)模的關(guān)系

2） 內(nèi)存占用率

圖14 描繪了4 種算法在facebookb30w, kosarak 30w, Enron30w, accidents30w 這4 組數(shù)據(jù)子集進(jìn)行集合相似度自連接計算過程中的內(nèi)存占用率，其中，F(xiàn)astTELP-SJ 在 處 理kosarak30w 和Enron30w 時 內(nèi) 存占用率峰值分別是其他3 種算法的2～3 倍，因為TELP-tree 在其任務(wù)2 的函數(shù)reduce運行過程中常駐內(nèi)存，這跟第1, 2 節(jié)的分析一致.但RP-PPJoin 和FSJoin 的候選集大，也有可能出現(xiàn)內(nèi)存占用率高的情況，如圖14（a）（d）.同時RP-PPJoin+Bitmap 的內(nèi)存占用率峰值始終最大，這是因為該算法需要為每個集合構(gòu)造相應(yīng)的位圖并保存在內(nèi)存中進(jìn)行計算.

Fig.14 Memory usage of four algorithms （t = 0.6）圖14 4 種算法的內(nèi)存占用率（t = 0.6）

3） 磁盤使用量

圖15 描繪了4 種算法在facebookb30w，kosarak 30w，Enron30w，accidents30w 這4 組數(shù)據(jù)子集上進(jìn)行集合相似度自連接計算過程中的磁盤使用量.當(dāng)閾值t= 0.6 時，F(xiàn)astTELP-SJ 在處理facebook30w，kosarak-30w，accidents30w 這3 個數(shù)據(jù)子集時的磁盤讀寫量最低，因為它的驗證計算都在內(nèi)存中完成，減少了I/O，此結(jié)論與第1, 2 節(jié)的分析和3.3.1 節(jié)運行時間相關(guān)的實驗結(jié)果分析相一致.尤其是RP-PPJoin 和RP-PPJoin+Bitmap，因它們可能產(chǎn)生重復(fù)驗證的冗余候選集，磁盤使用量最大，見圖15（c）（d）.而當(dāng)闕值t增大時，如t=0.9時，由于過濾策略的應(yīng)用，大量數(shù)據(jù)被過濾，各個算法的磁盤使用量都降低，差別也減少.

Fig.15 Disk usage amount of four algorithms圖15 4 種算法的磁盤使用量

3.4 小 結(jié)

基于3.1～3.3 節(jié)的實驗結(jié)果比較，當(dāng)閾值t比較高時，如在我們的實驗環(huán)境和數(shù)據(jù)下，t＞0.8時， 4 種算法的執(zhí)行性能差別不大.當(dāng)閾值t比較低時，我們有4 點實驗結(jié)論：

1） 高維大規(guī)模集合相似度自連接計算中TELPSJ 的運行效率最好且具有較好的可擴展性.

2） 低維大規(guī)模集合相似度自連接計算中PPCSJ 的運行效率最好.

3） 高維大規(guī)模集合相似度自連接計算中基于并行分布式計算模型MapReduce 和TELP-tree 設(shè)計的算法FastTELP-SJ 相對于TELP-SJ 有較好的加速比.

4） 大規(guī)模集合相似度自連接計算中FastTELPSJ 的運行效率優(yōu)于現(xiàn)有基于MapReduce 的3 類算法RP-PPJoin, RP-PPJoin + Bitmap, FS-Join.

4 結(jié)束語

數(shù)據(jù)的增長、集合規(guī)模的加大給現(xiàn)有集合相似度自連接算法帶來挑戰(zhàn).基于MapReduce 的并行分布式集合相似度自連接加速了計算，但當(dāng)閾值較低時現(xiàn)有算法生成了較大規(guī)模的候選集，執(zhí)行效率依然不理想.

為此，本文提出并設(shè)計采用頻繁模式樹及其派生結(jié)構(gòu)FP-tree*加速集合相似度自連接算法：1）設(shè)計面向基于FP-tree*的集合相似度自連接算法及加速其計算的2 階段過濾規(guī)則，減小FP-tree*的規(guī)模并提高樹遍歷效率；2）提出并構(gòu)建面向集合相似度自連接的遍歷效率更高的FP-tree 派生結(jié)構(gòu)-線性頻繁模式樹結(jié)構(gòu)TELP-tree 及基于其的算法TELP-SJ；3）設(shè)計基于MapReduce 和TELP-tree 的集合相似度自連接算法FastTELP-SJ.基于4 組真實應(yīng)用數(shù)據(jù)集，通過3組比較實驗從運行時間、內(nèi)存占用率、磁盤使用量等方面進(jìn)行對比實驗來評估FastTELP-SJ 的性能，實驗結(jié)果展現(xiàn)了FastTELP-SJ 較好運行性能和可擴展性.

FastTELP-SJ 算法將數(shù)據(jù)壓縮在內(nèi)存中進(jìn)行計算，帶來構(gòu)建樹和銷毀樹等運行期內(nèi)存管理開銷，同時，F(xiàn)astTELP-SJ 算法包含2 次MapReduce 任務(wù)，帶來運行期流程管理開銷.經(jīng)調(diào)研，文獻(xiàn)[39-40]設(shè)計了一種基于生命周期的內(nèi)存管理框架Deca，通過自動分析用戶定義的函數(shù)和數(shù)據(jù)結(jié)構(gòu)，預(yù)測其生命周期.基于該預(yù)測分配和釋放空間可提高系統(tǒng)垃圾回收效率，進(jìn)而提高內(nèi)存使用率.另外，文獻(xiàn)[41-42]提出了一種面向流數(shù)據(jù)和迭代任務(wù)流程管理降低能耗的資源共享框架F3C.我們將進(jìn)一步研究如何結(jié)合有效的內(nèi)存管理、流程管理框架構(gòu)建綠色高效的集合相似度連接計算.

作者貢獻(xiàn)聲明：馮禹洪發(fā)現(xiàn)問題、定義問題、提出算法思路和實驗方案；吳坤漢、黃志鴻、馮洋洲負(fù)責(zé)完成算法設(shè)計、實現(xiàn)、性能評估；陳歡歡、白鑒聰、明仲優(yōu)化算法和實驗方案.所有作者共同完善國內(nèi)外研究現(xiàn)狀調(diào)研、完成論文的撰寫和修改.