賈連印 奚建清 李孟娟 游進(jìn)國 劉勇 苗德成

(1.華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006;2.云南師范大學(xué)圖書館，云南昆明650092;3.昆明理工大學(xué)信息工程與自動化學(xué)院，云南昆明650500)

集合一直是研究者研究的熱點，在眾多涉及集合的問題中，集合相似度連接問題旨在從大量的集合中查找滿足特定相似度閾值的集合對.該問題廣泛存在于數(shù)據(jù)清洗［1-2］、近似重復(fù)判斷［3］、抄襲檢測［4］等領(lǐng)域.

需要注意的是，集合相似度連接問題不同于集合相似度查詢問題［5］.集合相似度查詢算法通常基于全部數(shù)據(jù)構(gòu)建靜態(tài)的索引結(jié)構(gòu)，同樣可用于實現(xiàn)集合相似度連接算法.但高效的集合相似度連接算法為了避免出現(xiàn)重復(fù)的結(jié)果對而通常在部分?jǐn)?shù)據(jù)基礎(chǔ)上以動態(tài)遞增的方式構(gòu)建索引，因此具有更優(yōu)的性能.

集合相似度問題同樣不同于被廣泛研究的集合包含問題［6-11］.集合包含問題通常以集合包含查詢?yōu)榛A(chǔ)，可分為子集查詢、超級查詢和等值查詢.集合包含查詢通常用于查詢一個集合完全包含或包含于另一個集合.而集合相似度查詢或連接則著重于研究集合之間包含的程度.

近年來，研究者提出了多種不同的算法來解決集合相似性連接問題，例如算法 SSJoin［1］、PARTENUM 算法［2］、WTENUM 算法［2］、topk-join 算法［12］、MergeOpt算法［13］等.

眾多算法中，Bayardo等［14］提出的 All-pair算法、Xiao等［3］提出的 PPJoin算法具有良好的伸縮性，能非常高效地擴(kuò)展到上百萬記錄的All-pair問題的計算.

然而，這類算法通?；诜聪蛩饕Y(jié)構(gòu)并且基于生成－測試的框架來執(zhí)行.它們首先在生成階段生成候選集，然后在測試階段對候選集進(jìn)行逐一驗證，從而得到最終的結(jié)果.當(dāng)生成的候選集非常大時，系統(tǒng)的性能不可避免地會降低.為了解決這個問題，文中設(shè)計了一種動態(tài)trie索引結(jié)構(gòu)——DTI結(jié)構(gòu)，DTI采用流的思想根據(jù)已讀入的記錄動態(tài)地創(chuàng)建trie索引;在DTI基礎(chǔ)上，文中提出了高效的Dtrie-allpair算法，并通過實例模擬對該算法進(jìn)行了驗證.

Trie-Join算法［15］同樣基于trie結(jié)構(gòu)研究集合相似度連接問題，然而該算法主要關(guān)注于編輯距離謂詞，Dtrie-allpair則關(guān)注于T-覆蓋謂詞.T-覆蓋更具有一般性，能用于解決其它相似度謂詞.

1 相關(guān)定義

記錄集:有限記錄的集合稱為記錄集.

元素頻率:指一個元素在整個數(shù)據(jù)庫中出現(xiàn)的次數(shù).

序:指記錄或元素在數(shù)據(jù)庫中出現(xiàn)的相對順序.可分為元素序(元素在記錄中的順序)和記錄序(記錄在數(shù)據(jù)庫中的順序)兩種.

常見的元素序有值序和頻率序兩種.值序是指按照元素大小安排元素在記錄中的順序，分為值升序和值降序;頻率序是指按元素頻率安排元素在記錄中的順序，分為頻率升序和頻率降序.

常見的記錄序為長度序.所謂長度序，是指按照記錄中元素數(shù)量安排記錄在數(shù)據(jù)庫中的順序，分為長度升序和長度降序.

文中假設(shè)集合中元素為整型且不是多重集，即集合中不含重復(fù)元素.

本研究主要關(guān)注T-覆蓋連接，它可用于解決其它相似度謂詞的連接問題，如JACCARD、COSINE、DICE等，也是研究集合相似度連接的基礎(chǔ).下面給出T-覆蓋連接的正式定義.

定義1 T-覆蓋連接:給定兩個記錄集X和Y以及一個覆蓋閾值T，找出所有＜x，y＞對(x∈X且y∈Y)，使得x和y至少擁有T個公共元素(同時在記錄x和y中出現(xiàn)的元素).即

文中著重于自連接，即記錄集X=Y的情況，但本研究的工作可擴(kuò)展到X≠Y的情況.

2 傳統(tǒng)的T-覆蓋算法

2.1 All-pair算法

All-pair算法是一種基于反向索引的算法，在MergeOpt算法［13］基礎(chǔ)上發(fā)展而來，采用生成－測試的框架來執(zhí)行.該算法采用流的思想，對每一個到來的記錄x，通過索引探測已看到的每一個記錄y，比較其是否與x有足夠的相似度.為了檢測x和y的相似度，只需對y的部分記錄構(gòu)建索引即可.為了確定y中需要索引的長度，該算法基于以下定理.

證明 由x的T－1個后綴和y的T－1個后綴最多有T－1個公共元素易見定理1成立.

因此，為了確定記錄x和記錄y是否有足夠的相似度，該算法只需為y的個前綴元素建立反向索引即可.

在查找記錄x的相似對之前，用x的每一個前綴元素p去探測由在x之前出現(xiàn)的所有記錄的前綴建立的反向索引，p所對應(yīng)的反向列表中的每一個記錄y'可被看作與x相似的一個候選記錄.

為了檢測x和其任一候選記錄y'的覆蓋，該算法需要執(zhí)行一個驗證階段來檢測x和y'的實際覆蓋值.

為了提高效率，All-pair算法引入了長度過濾機(jī)制，如果，則y'不可能成為x的候選集.該算法要求對數(shù)據(jù)庫中所有記錄R按長度從小到大的順序進(jìn)行排列;并且按照某種特定順序?qū)τ涗浿性剡M(jìn)行排序來加快候選集檢測的速度.

該算法采用谷歌稠密哈希(Google Dense Hash)來存儲生成的候選集.整個算法可分為3個階段:生成候選集階段、驗證階段及索引階段.生成候選集階段約需F次hash插入或更新操作，F(xiàn)為通過長度過濾的記錄中的全部元素數(shù)量;驗證階段需對記錄和每一個候選集的T－1個后綴進(jìn)行掃描，約次元素訪問操作，C為整個算法的總候選集數(shù)量為記錄的平均長度;索引階段需I次索引插入操作，I為 F中被索引的元素數(shù)，且存在I=F－n(T－1)，n為通過長度過濾的記錄數(shù)量.

算法的候選集大小是影響All-pair算法性能最重要的參數(shù)，但其很難精確估量.最壞情況下，n條記錄的數(shù)據(jù)集可能考慮的候選集數(shù)量為C=n(n－1)/2.

與普通反向索引中反向列表為ID的有序序列不同，All-pair的反向列表結(jié)點由ID以及指向該記錄未索引部分?jǐn)?shù)據(jù)的指針組成.該算法需在內(nèi)存保留被索引的記錄，因此反向列表的空間需求為2I+F個整型空間(文中假設(shè)元素、ID和指針各需一個整型內(nèi)存空間)，另外該算法最大需有存儲n－1個候選集的hash空間(All-pair的反向索引目錄部分采用直接索引，需大于最大元素大小的索引大小).

2.2 PPJoin算法

All-pair算法的缺點在于可能生成過于龐大的候選集，從而導(dǎo)致算法性能降低.PPJoin算法［3］在All-pair算法的長度過濾基礎(chǔ)上引入前綴過濾和位置過濾來改進(jìn)All-pair算法的性能.

前綴過濾要求按照頻率升序?qū)λ杏涗涍M(jìn)行排序.因前綴中的元素在數(shù)據(jù)庫中出現(xiàn)的頻率相對較低，因此，探測到的候選集會大大減少.

位置過濾要求在元素E的反向列表中同時索引記錄x和E 在x中的位置pos，即〈x，pos〉對.位置pos同樣有助于快速過濾不符合條件的候選集，從而降低候選集大小.對T-覆蓋而言，因其是固定閾值T的，故所有大于T的記錄均有相同的T－1個未索引的后綴，這也使得任一候選記錄y'和當(dāng)前記錄x潛在的覆蓋值總是大于等于T，PPJoin的位置過濾不會起作用，故文中的PPJoin并未應(yīng)用位置過濾.

PPJoin算法生成候選集階段需I次hash操作;驗證階段約需要次元素訪問操作為當(dāng)前元素和候選集通過索引已檢測到的覆蓋值;索引階段同樣需要I次索引插入操作.

PPJoin算法的反向列表結(jié)點由ID、指向記錄的指針，以及記錄的大小組成.因此，其反向列表部分空間需求為3I+F，另外同樣需要和All-pair相同的存儲候選集的空間.

文獻(xiàn)［3］進(jìn)一步提出了通過海明距離對候選集后綴進(jìn)行有效過濾的PPJoin+算法.

3 DTI索引結(jié)構(gòu)及基于DTI的相似度連接算法

與All-pair和PPJoin算法類似，文中提出的算法同樣基于流的思想，對每一個到來的記錄x，通過索引探測符合相似度閾值T的所有的記錄y，這樣對相同的相似對〈x，y〉和〈y，x〉只需統(tǒng)計一次.與上述兩個算法不同之處在于:(1)文中提出的DTI索引是基于trie的動態(tài)索引結(jié)構(gòu)，而非基于反向索引結(jié)構(gòu);(2)DTI基于y的所有元素(而非部分元素)構(gòu)建索引;(3)通過基于DTI結(jié)構(gòu)的算法可以直接得到T-覆蓋查詢的結(jié)果，而無需生成任何候選集，從而可以提高算法執(zhí)行的效率.

3.1 DTI結(jié)構(gòu)

DTI結(jié)構(gòu)的基本思想是:將數(shù)據(jù)庫中的每條記錄映射為一條從根到葉的trie路徑.記錄中的每一個元素映射到trie中的一個結(jié)點，多條記錄的公共前綴映射為trie中的一條公共的路徑.

DTI結(jié)構(gòu)由目錄和trie兩部分組成.DTI的目錄和反向索引的目錄相似，由有限全局U中的元素構(gòu)成.每一個目錄項包含U中一個獨立的元素以及指向該元素對應(yīng)的第一個trie結(jié)點的指針.表1給出了一個包含5條記錄的簡單值升序數(shù)據(jù)庫，以表1的前4條記錄創(chuàng)建的DTI結(jié)構(gòu)如圖1所示，其中root為一個空的根結(jié)點.

表1 一個簡單的值升序數(shù)據(jù)庫Table 1 A simple database with value-ascending order

圖1 根據(jù)表1前4條記錄創(chuàng)建的DTI結(jié)構(gòu)Fig.1 DTI created for the first 4 records of Table 1

DTI的trie部分主要由trie結(jié)點組成，trie結(jié)點的結(jié)構(gòu)如圖2所示.

圖2 trie結(jié)點結(jié)構(gòu)Fig.2 Structure of trie node

圖2中的各字段描述如下:

Elem，代表元素E本身;trie結(jié)點N代表的元素E稱之為N的源，結(jié)點N則稱為元素E的一個出現(xiàn);若R為任意包含E的記錄，稱R映射的trie路徑上的E的出現(xiàn)為E關(guān)于R則的出現(xiàn);元素E在trie中可有多個出現(xiàn)，但E關(guān)于記錄R的出現(xiàn)最多只有一個.

NodeLink，鏈接到E的下一個出現(xiàn)的指針;E的所有出現(xiàn)的集合稱之為E的出現(xiàn)集，出現(xiàn)集可以方便地通過目錄中該元素的指向trie結(jié)點的指針和NodeLink獲取.

Children，指向當(dāng)前結(jié)點子結(jié)點集的指針.

Parent，指向當(dāng)前結(jié)點父結(jié)點的指針.

NodeInvertedList，又稱結(jié)點反向列表(簡稱NIL)，是所有映射路徑中包含從根到當(dāng)前結(jié)點的前綴路徑的記錄的ID的集合;文中規(guī)定，根結(jié)點的NIL為所有記錄的ID的全集;各個結(jié)點的NIL見圖1中結(jié)點左側(cè)的集合.

Depth，用于在查詢過程中設(shè)置查詢深度，見下節(jié).

圖1中，元素a的唯一出現(xiàn)即結(jié)點1(結(jié)點右側(cè)數(shù)字表示結(jié)點號)，其結(jié)點前綴路徑為root a，而映射路徑包含這個結(jié)點前綴路徑的記錄分別是記錄0、2(ID 為0、2 的記錄).因此，結(jié)點1 的 NIL 為{0，2}.結(jié)點的NIL可以在DTI的創(chuàng)建過程中生成.

創(chuàng)建DTI結(jié)構(gòu)的算法非常容易，具體算法文中不再贅述.

定理2 DTI中，任一非根結(jié)點的NIL是其父結(jié)點的NIL的子集.

證明 從結(jié)點前綴路徑的包含關(guān)系易見.

3.2 Dtrie-allpair:基于DTI的相似度連接算法

為了有效描述Dtrie-allpair算法，文中引入查詢結(jié)點和查詢深度的概念.

定義2 查詢結(jié)點:所有源包含于當(dāng)前記錄x中的結(jié)點.

定義3 查詢深度:查詢結(jié)點的查詢深度定義為從根到該查詢結(jié)點的路徑(含該結(jié)點)中查詢結(jié)點的數(shù)量.查詢結(jié)點N的查詢深度用DN表示.根結(jié)點非查詢結(jié)點，為了便于處理，文中規(guī)定根結(jié)點的查詢深度為0.查詢深度為D的查詢結(jié)點稱之為D-結(jié)點.

給定圖3所示DTI結(jié)構(gòu)和新到的當(dāng)前記錄x={b，e，g}，可見，結(jié)點5為查詢結(jié)點，其查詢深度為3，因為從root到結(jié)點5的路徑中，有結(jié)點2、3和53個查詢結(jié)點.目錄中深色背景為當(dāng)前記錄元素，trie中深色背景結(jié)點為查詢結(jié)點.

圖3 在DTI上執(zhí)行查詢Fig.3 Executing query on DTI

定理3 對當(dāng)前記錄x而言，所有T-結(jié)點的NIL的并集為滿足x的T-覆蓋查詢的結(jié)果.

證明 首先證明正確性，也即是證明所有T-結(jié)點的NIL的并集滿足命題.

設(shè)N'為任意T-結(jié)點，則從該結(jié)點到根的路徑上有T個查詢結(jié)點，故該結(jié)點的NIL對應(yīng)的所有記錄均包含這T個結(jié)點的源.另外根據(jù)定義2，這T個查詢結(jié)點的源均出現(xiàn)在x中，故正確性成立.

其次證明完備性，即證明T-結(jié)點的NIL的并集包含了相似度查詢的全部結(jié)果.

N'為任意T-結(jié)點，Nd為N'的任一子孫結(jié)點，Na為N'的祖先結(jié)點.首先，由定理2可知，Nd的NIL是N'的NIL的子集，Nd的NIL已包含在T-結(jié)點的NIL中;其次，由定理2可知，Na的NIL為N'的NIL的超集，可分為終結(jié)于T層或T層查詢結(jié)點之后的ID與終結(jié)于T層查詢結(jié)點之前的ID兩部分，第1部分ID顯然包含在T層結(jié)點的NIL中，對于第2部分ID，其從根到葉結(jié)點的路徑上查詢結(jié)點數(shù)量小于T，故該部分不可能符合要求.

綜上可見，所有符合條件的結(jié)果均包含在T-結(jié)點的NIL的并集中，故定理得證.

如圖3所示DTI結(jié)構(gòu)和當(dāng)前記錄x={b，e，g}，T=2，則2-結(jié)點為結(jié)點3和10，其 NIL的并集為{0，3}，故ID為0和3的兩個記錄和x的覆蓋大于等于2.

基于上述定義和定理，文中的問題就轉(zhuǎn)換到如何快速有效地查找T-結(jié)點上來.

對每一個查詢結(jié)點N，可通過式(1)計算其查詢深度:

式中，N.Pred表示結(jié)點N的前驅(qū)查詢結(jié)點，即從該查詢結(jié)點到根的路徑中距離N最近的查詢結(jié)點.為此，提出了查找任意查詢結(jié)點的前驅(qū)查詢結(jié)點的算法(FindPredecessor算法)，如下所示:

FindPredecessor算法中，遞歸判斷查詢結(jié)點N的父結(jié)點是否是查詢結(jié)點.在判斷某結(jié)點是否是查詢結(jié)點時，基于以下定理，只需要判斷該結(jié)點的源是否存在于x的前面一部分元素中:

定理4 對特定的元素序而言，若E為x中一個元素，N為E的任一出現(xiàn)，Na為N的任一祖先結(jié)點，則Na的源如在x中，其位置必在E之前.

證明 由x中元素序靠前的元素映射的結(jié)點為元素序靠后的元素映射結(jié)點的祖先結(jié)點易見定理成立.

根據(jù)定理4，若E在x的位置為pos，要判斷Na是否是查詢結(jié)點，則只需查找其源是否存在于x的前pos－1個元素中即可.故而在FindPredecessor算法中，引入?yún)?shù)查詢集下標(biāo)參數(shù)k，用來減少比較次數(shù).

圖3中，結(jié)點5的源為g，為記錄{b，e，g}的第3個元素.若要判斷其父結(jié)點——結(jié)點4是否是查詢結(jié)點，無需判斷結(jié)點4的源——元素f是否存在于整個查詢集中，只需判斷f是否存在于前兩個元素{b，e}中即可.

在實現(xiàn)FindPredecessor算法的基礎(chǔ)上實現(xiàn)Get-OverLapPair算法，如下所示:

GetOverLapPair算法執(zhí)行如下:對x中的第一個元素的所有出現(xiàn)，因其之前沒有其它查詢結(jié)點，故可以安全地將其查詢深度置為1;然后依次對x中其它元素的每一個出現(xiàn)調(diào)用FindPredecessor算法查找其前驅(qū)查詢結(jié)點，并按照式(1)計算其查詢深度;計算的查詢深度直接存儲于該結(jié)點的Depth域中.如果某個查詢結(jié)點的查詢深度等于T，則將該結(jié)點的NIL中每一個ID與x.ID組成的結(jié)果對加入到結(jié)果集中.

完整的Dtrie-allpair算法如下所示.在算法中，應(yīng)用了長度過濾，如果，則不對x進(jìn)行任何處理.

3.3 算法分析

由Dtrie-allpair算法可見，該算法只需遍歷數(shù)據(jù)庫一次，對每一條記錄x先查詢后索引.由于應(yīng)用長度過濾，因此覆蓋閾值越高，過濾后需要處理的記錄就越少.

trie結(jié)點為DTI結(jié)構(gòu)的主要空間開銷.若M為DTI中的trie結(jié)點數(shù)量，每個結(jié)點除NIL域外的其余部分，需5個整型空間.易見，所有結(jié)點的NIL中ID的數(shù)量等于索引的元素數(shù)量F，故trie結(jié)點共需空間為5M+F.

3.4 進(jìn)一步優(yōu)化

第3.1節(jié)中根據(jù)值升序來創(chuàng)建DTI結(jié)構(gòu).本節(jié)進(jìn)一步通過開發(fā)其它序來提升Dtrie-allpair算法的性能.

頻率降序按元素在整個數(shù)據(jù)庫中的頻率從高到低的順序安排元素在各記錄中位置，這使得根據(jù)頻率降序創(chuàng)建的DTI結(jié)構(gòu)具有最少的結(jié)點，從而降低了自連接所需訪問的節(jié)點數(shù)，提升了算法的性能.表1數(shù)據(jù)庫對應(yīng)的頻率降序數(shù)據(jù)庫如表2所示.

表2 表1對應(yīng)的頻率降序數(shù)據(jù)庫Table 2 Frequncy-descending order database of Table 1

根據(jù)表2的前4條記錄創(chuàng)建的DTI結(jié)構(gòu)如圖4所示.可見采用頻率序創(chuàng)建的DTI僅包含10個結(jié)點，而圖1的DTI包含11個結(jié)點.

長度升序按元素數(shù)量從低到高的順序安排記錄在數(shù)據(jù)庫中的位置，這同樣有助于提升算法的性能.通過長度升序，并不會降低索引全部記錄最終創(chuàng)建的DTI結(jié)點數(shù)，但由于較短的記錄優(yōu)先被索引，故在自連接過程中傾向于訪問更少的結(jié)點.表1數(shù)據(jù)庫對應(yīng)的長度升序數(shù)據(jù)庫如表3所示.根據(jù)表3前4條記錄創(chuàng)建的DTI結(jié)構(gòu)如圖5所示.

圖4 根據(jù)表2前4條記錄創(chuàng)建的DTI結(jié)構(gòu)Fig.4 DTI created for the first 4 records of Table 2

表3 表1對應(yīng)的長度升序數(shù)據(jù)庫Table 3 Length-ascending order database of Table 1

圖5 根據(jù)表3前4條記錄創(chuàng)建的DTI結(jié)構(gòu)Fig.5 DTI created for the first 4 records of Table 3

對表1中的5條記錄，在DTI中查詢時需要訪問的結(jié)點數(shù)依次為 0、1、2、3、5，共需 11 次結(jié)點訪問;而表3中長度降序的5條記錄需訪問的結(jié)點數(shù)依次為 0、0、2、2、5，只需9 次結(jié)點訪問.

通過組合頻率降序和長度升序，可同時降低創(chuàng)建的結(jié)點和訪問的結(jié)點，進(jìn)一步提升Dtrie-allpair算法的性能.因篇幅限制，具體分析文中不再贅述.

4 實驗

4.1 實驗環(huán)境

為了評估 Dtrie-allpair算法的性能，將 Dtrie-allpair算法和All-pair算法及PPJoin算法進(jìn)行對比.實驗主要硬件平臺:CPU Intel Core i5-2410M@2.30GHz，內(nèi)存 4 GB;軟件環(huán)境:Windows732 位，Microsoft Visual Studio C++2008.

采用兩個不同的數(shù)據(jù)集驗證文中的算法.第一個數(shù)據(jù)集為 UCI KDD Archive 的 msweb［16］數(shù)據(jù)集，包含用戶對www.microsoft.com站點虛擬區(qū)域一周的訪問日志.每個集合表示一次用戶會話時訪問的區(qū)域的集合，共有32711條記錄，詞匯表中包含294個獨立元素，記錄最大勢為35.

第二個數(shù)據(jù)集同樣采用UCI KDD Archive的msnbc數(shù)據(jù)集，共有989818條記錄，該數(shù)據(jù)集詞匯表較小，僅包含17個獨立元素，最大記錄長度為17，平均記錄長度為5.7.

4.2 算法比較

對3種算法，均采用長度過濾，對 All-pair和PPJoin算法，只索引其前綴.

3種算法均要求對數(shù)據(jù)進(jìn)行相應(yīng)的預(yù)處理.Allpair算法要求數(shù)據(jù)集按記錄長度升序有序，記錄內(nèi)的元素同樣升序排序，以加快候選集的校驗;PPJoin除需All-pair的要求外，還需對數(shù)據(jù)集按頻率升序排序;Dtrie-allpair在組合頻率降序和長度升序時相對PPJoin并不會帶來更多的預(yù)處理代價.預(yù)處理的時間開銷所占比例非常小，且通常可以離線進(jìn)行，因篇幅限制，文中不對預(yù)處理過程做更詳盡的介紹.除特別聲明外，以下對Dtrie-allpair算法采用的數(shù)據(jù)集均采用組合頻率降序和長度升序進(jìn)行預(yù)處理.

對3種算法，分別在相似度閾值 T為2、4、6、8、10時各執(zhí)行一次自連接.msweb數(shù)據(jù)集下3種算法的執(zhí)行時間如圖6所示.

圖6 msweb數(shù)據(jù)集下3種算法的自連接執(zhí)行時間Fig.6 Self-join time of three algorithms under msweb data

由圖6可見，Dtrie-allpair算法的執(zhí)行效率高于All-pair、PPJoin兩種算法，并且在閾值較小時具有更大的優(yōu)勢.T=2時，Dtrie-allpair算法執(zhí)行自連接僅需0.5s，而 All-pair算法、PPJoin算法分別需要90s、54 s，Dtrie-allpair算法的效率提高近兩個數(shù)量級;T=10時，Dtrie-allpair算法約需0.09 s時間完成自連接，而All-pair算法和PPJoin算法分別需要0.5 s和0.3s來完成.

對msnbc數(shù)據(jù)集，實驗中觀察到類似的結(jié)果，對T=2的情況，All-pair算法和PPJoin算法均不能在1h內(nèi)結(jié)束.msnbc數(shù)據(jù)集下3種算法的執(zhí)行時間如圖7所示.

圖7 msnbc數(shù)據(jù)集下3種算法的自連接執(zhí)行時間Fig.7 Self-join time of three algorithms under msnbc data

圖8 msweb數(shù)據(jù)集下不同算法產(chǎn)生的候選集及實際相似對數(shù)量Fig.8 Generated candidates and number of real similar pairs of different algorithms under the msweb data

All-pair算法和PPJoin算法效率較低的一個重要原因在于，這兩個算法需要生成大量的候選集，然后對候選集逐一驗證.覆蓋閾值越小，需要驗證的候選集和最終的結(jié)果集就越大，因此，需要的執(zhí)行時間也就越長.而Dtrie-allpair算法不產(chǎn)生任何候選集，通過索引可以得到直接的結(jié)果，因此效率大大提高.msweb數(shù)據(jù)集下All-pair算法、PPJoin算法需要驗證的候選集數(shù)量以及實際相似對的數(shù)量如圖8所示.圖例中Result代表最終結(jié)果對，對Result而言，縱坐標(biāo)代表最終結(jié)果對數(shù)量;對All-pair算法和PPJoin算法而言，縱坐標(biāo)代表候選集數(shù)量.

4.3 序?qū)trie-allpair算法的影響

為了考察不同的序及其組合對Dtrie-allpair算法的影響，文中對數(shù)據(jù)集分別按值升序、頻率降序、值升序加長度升序以及頻率降序加長度升序進(jìn)行相應(yīng)的預(yù)處理.在msweb數(shù)據(jù)集下，對不同預(yù)處理的數(shù)據(jù)集執(zhí)行Dtrie-allpair算法得到的自連接時間和訪問的節(jié)點數(shù)分別如圖9和10所示.從圖中可見，頻率降序和長度升序組合在自連接過程中訪問最少的節(jié)點數(shù)，在T=2時，其訪問節(jié)點數(shù)僅為只用值升序的1/4，從而需要的執(zhí)行時間也大大降低.

圖9 msweb數(shù)據(jù)集下4種序的自連接時間Fig.9 Self join time of four kinds of orders under the msweb data

圖10 msweb數(shù)據(jù)集下4種序訪問的節(jié)點數(shù)Fig.10 Nodes accessed of four kinds of orders under the msweb data

5 結(jié)語

傳統(tǒng)的T-覆蓋算法通常是基于生成－測試的框架來執(zhí)行，它們需要在測試階段對成階段生成的候選集逐一驗證，當(dāng)候選集非常大時，系統(tǒng)的性能不可避免地會降低.針對傳統(tǒng)算法這一不足，文中提出了一種DTI結(jié)構(gòu)，并基于該結(jié)構(gòu)構(gòu)建了Dtrie-allpair算法，通過該算法可以直接得到allpair連接的結(jié)果，而不產(chǎn)生任何候選集，有效克服了傳統(tǒng)算法需生成并驗證候選集帶來的開銷.通過實驗對Dtrie-allpair算法與All-pair算法、PPJoin算法進(jìn)行對比，結(jié)果表明Dtrie-allpair算法具有明顯的優(yōu)勢;通過頻率降序和長度升序組合可有效降低DTI中訪問的結(jié)點數(shù)，從而提升Dtrie-allpair算法的性能.Dtrie-allpair算法也存在一定的缺點，主要在于DTI結(jié)構(gòu)傾向于需要更高的空間開銷，這是下一步研究中需要解決的問題.

［1］ Chaudhuri S，Ganti V，Kaushik R.A primitive operator for similarity joins in data cleaning［C］∥Proceedings of the 22nd International Conference on Data Engineering.Atlanta:IEEE Computer Society，2006:5-16.

［2］ Arasu A，Ganti V，Kaushik R.Efficient exact set-similarity joins［C］∥Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul:ACM Press，2006:918-929.

［3］ Xiao C，Wang W，Lin X，et al.Efficient similarity joins for near duplicate detection［C］∥Proceedings of the 17th International Conference on World Wide Web.Beijing:ACM Press，2008:131-140.

［4］ Hoad T，Zobel J.Methods for identifying versioned and plagiarized documents［J］.Journal of the American Society for Information Science and Technology，2003，54(3):203-215.

［5］ Li C，Lu J，Lu Y.Efficient merging and filtering algorithms for approximate string searches［C］∥Proceedings of the 24nd International Conference on Data Engineering.Cancún:IEEE Computer Society，2008:257-266.

［6］ Helmer S，Moerkotte G.A performance study of four index structures for set-valued attributes of low cardinality［J］.The International Journal on Very Large Data Bases，2003，12(3):244-261.

［7］ Helmer S，Aly R，Neumann T，et al.Indexing set-valued attributes with a multi-level extendible hashing scheme［C］∥Proceedings of the 18th International Conference of Database and Expert Systems Applications.Regensburg:Springer-Verlag，2007:98-108.

［8］ Mamoulis N.Efficient Processing of joins on set-valued attributes［C］∥Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data.San Diego:ACM Press，2003:157-168.

［9］ Terrovitis M，Passas S，Vassiliadis P，et al.A combination of trie-trees and inverted files for the indexing of set-valued attributes［C］∥Proceedings of the 15th ACM International Conference on Information and Knowledge Management.Arlington:ACM Press，2006:728-737.

［10］ Hossain S，Jamil H M.A hybrid index structure for setvalued attributes using itemset tree and inverted list［C］∥Proceedings of the 21st international Conference on Database and Expert Systems Applications.Bilbao:Springer-Verlag，2010:349-357.

［11］ Agrawal P，Arasu A，Kaushik R.On indexing error-tolerant set containment［C］∥Proceedings of the 2010 International Conference on Management of Data.Indianapolis:ACM Press，2010:927-938.

［12］ Xiao C，Wang W，Lin，X，et al.Top-k set similarity joins［C］∥Proceedings of the 25nd International Conference on Data Engineering.Shanghai:IEEE Computer Society，2009:916-927.

［13］ Sarawagi S，kirpal A.Efficient set joins on similarity predicates［C］∥Prceedings of the 2004 ACM SIGMOD Intevnational Conference on Management of Data.Paris:ACM Pvess，2004:743-745.

［14］ Bayardo R，Ma Y，Srikant R.Scaling up all pairs similarity search［C］∥Proceedings of the 16th International Conference on World Wide Web.Banff:ACM Press，2007:131-140.

［15］ Wang J，Li G，F(xiàn)eng J，et al.Trie-join:efficient triebased string similarity joins with edit distance constraints［J］.Proceedings of the VLDB Endowment，2010，3(1/2):1219-1230.

［16］ Bay S D，Kibler D，Pazzani M J，et al.The uci kdd archive of large data sets for data mining research and experimentation［J］.ACM SIGKDD Explorations Newsletter，2000，2(2):8185.