于長(zhǎng)永, 王雯函, 溫秀靜, 趙宇海

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 遼寧 沈陽(yáng) 110169)

相似性查找和相似性連接是數(shù)據(jù)庫(kù)中處理和分析數(shù)據(jù)的重要且基礎(chǔ)的操作.相似性查找旨在查詢與給定query滿足相似性條件的數(shù)據(jù)庫(kù)中的所有記錄.相似性連接旨在從兩個(gè)集合中找到所有相似的對(duì).它們有許多實(shí)際應(yīng)用,如數(shù)據(jù)清理與集成、近似重復(fù)檢測(cè)和信息提取等.例如當(dāng)兩個(gè)購(gòu)物網(wǎng)站要合并時(shí),兩個(gè)網(wǎng)站對(duì)同一商品的描述不完全一致,此時(shí)就需要找出兩個(gè)網(wǎng)站中的同一商品并最終合并.因?yàn)樵摂?shù)據(jù)集很大,高效處理數(shù)據(jù)是一種重要需求,所以相似性連接在該情況下是一種必不可少的操作.

對(duì)于傳統(tǒng)的Jaccard算法,根據(jù)過濾算法原理,大致可分為以下三種類型:①基于前綴過濾的算法;②基于鴿籠和劃分思想的過濾算法;③基于樹型數(shù)據(jù)結(jié)構(gòu)的過濾算法.前綴過濾算法是基于兩個(gè)數(shù)據(jù)的前綴至少共享一個(gè)元素來(lái)實(shí)現(xiàn)的[1-3].文獻(xiàn)[1]首次提出了前綴過濾的思想,并利用倒排索引實(shí)現(xiàn)了快速的相似性連接算法；文獻(xiàn)[2]通過將各記錄中的元素按照頻率由小到大的順序排序優(yōu)化了前綴過濾；文獻(xiàn)[3]進(jìn)一步縮小了前綴的長(zhǎng)度，利用共享元素的位置信息對(duì)候選進(jìn)行位置過濾，而且該文還對(duì)位置過濾的思想進(jìn)行推廣,提出了后綴過濾.基于鴿籠和劃分的過濾算法[4-6]主要思想是先根據(jù)鴿籠原理將每條記錄劃分為特定個(gè)數(shù)的不相交的段,再將這些段作為簽名構(gòu)建索引,最后計(jì)算出至少有一個(gè)共有段的記錄對(duì)的集合作為候選集.文獻(xiàn)[4]首次利用鴿籠原理提出了PartEnum；文獻(xiàn)[5]首次提出了基于全局元素劃分的鴿籠過濾算法；文獻(xiàn)[6]則在鴿籠原理的基礎(chǔ)上進(jìn)行了優(yōu)化,提出了一個(gè)新的過濾框架來(lái)覆蓋基于鴿籠原理的過濾框架,并且大多數(shù)基于鴿籠原理進(jìn)行分區(qū)的算法都有可能通過采用這個(gè)新原理來(lái)提高過濾功能.基于樹型數(shù)據(jù)結(jié)構(gòu)的過濾算法[7-8]與上述算法不同,它們不生成簽名來(lái)構(gòu)建倒排索引,而是將記錄組織到樹中,在樹中進(jìn)行過濾.

由于傳統(tǒng)的相似性連接問題在尋找相似對(duì)時(shí)有一些情況并不適用.例如{sweet,hot}和{hit,sweot},雖然它們很相似,但是不論是基于token的相似性函數(shù)或者基于字符的相似性函數(shù),它們的相似度都很低,并且基于token的相似性函數(shù)的相似度甚至為0,所以文獻(xiàn)[9]首次提出了模糊相似性連接問題,利用該算法提出的token敏感簽名在前綴過濾的基礎(chǔ)上進(jìn)行過濾可減少候選的數(shù)量；并且該算法在記錄級(jí)使用基于token的相似性函數(shù),而在元素級(jí)僅僅支持基于字符的相似性函數(shù).文獻(xiàn)[10]則在記錄級(jí)以及元素級(jí)都支持基于token的相似性函數(shù).其在前綴過濾生成簽名的部分進(jìn)行了改進(jìn),利用該算法生成的簽名以及其提出的檢測(cè)過濾器和最近鄰過濾器進(jìn)行過濾可大量減少候選的數(shù)量,但它在過濾的過程中并沒有考慮到token的長(zhǎng)度、元素的長(zhǎng)度以及token在元素中的位置對(duì)過濾性能的影響,所以其過濾效率并不是很高.由于文獻(xiàn)[11]是基于鴿籠原理劃分記錄中的元素來(lái)生成簽名,共享同一簽名的元素對(duì)應(yīng)的記錄視為候選對(duì),但由于該算法并沒有考慮到記錄中匹配的元素的個(gè)數(shù)對(duì)整體相似性的影響,在記錄之間一旦有匹配的元素就將其視為候選對(duì),造成候選集中假陽(yáng)性較高,并且由于該算法通過將全局元素劃分來(lái)對(duì)應(yīng)各個(gè)元素的劃分,所以部分元素的劃分中可能生成空集,但沒有考慮到出現(xiàn)空集時(shí)的處理辦法.為了解決這些問題,本文提出了一個(gè)基于動(dòng)態(tài)雙重前綴的相似性連接算法.與之前的基于前綴過濾算法不同的是,之前的算法采用固定前綴,而本文采用了雙重前綴方法,即在查找候選以及構(gòu)建索引時(shí)使用不同的前綴來(lái)提高過濾效力.在此基礎(chǔ)上又對(duì)雙重前綴過濾方法進(jìn)行了優(yōu)化,在保證不漏解的情況下取各種前綴生成的候選集合的交集來(lái)縮小候選集合.還設(shè)計(jì)了一種預(yù)驗(yàn)證方法來(lái)減少驗(yàn)證階段所花費(fèi)的不必要的時(shí)間.

1 問題定義

與之前的研究[9-11]一樣,本文也采用fuzzy overlap來(lái)實(shí)現(xiàn)模糊相似性連接.給定兩條記錄R與S和元素級(jí)相似性閾值δ,構(gòu)建一個(gè)二部圖G=((X,Y),E),X與Y中的頂點(diǎn)分別是記錄R與S中的元素.對(duì)于任意的兩個(gè)元素ri和sj,如果sim(ri,sj)≥δ,在二部圖ri和sj之間會(huì)存在一條邊,該邊的權(quán)重為ri和sj的相似值.下面是fuzzy overlap的定義.

下面利用fuzzy overlap來(lái)定義帶有元素級(jí)相似性閾值δ限制的記錄級(jí)相似性函數(shù).

Fuzzy-Jaccard Similarity:

Fuzzy-Dice Similarity:

Fuzzy-Cosine Similarity:

2 基于任選前綴的相似性連接算法

2.1 任選前綴

對(duì)于Jaccard相似性,若元素ri和sj,滿足sim(ri,sj)≥δ,則|ri∩sj|≥max{「δ|ri|?,「δ|sj|?},即ri和sj至少共享max{「δ|ri|?,「δ|sj|?}個(gè)token.將ttoken=max{「δ|ri|?,「δ|sj|?}稱為元素級(jí)overlap閾值.

下面利用記錄級(jí)fuzzy overlap閾值trecord和元素級(jí)overlap閾值ttoken定義模糊Jaccard相似性連接問題中記錄的雙重任選前綴.

根據(jù)定理1和上面的共享元素與共享token的數(shù)量,很容易得到以下的結(jié)論:

2)ri和sj滿足長(zhǎng)度過濾;

3)ri和sj對(duì)于共享token滿足位置過濾.

基于定理2,提出了基于雙重任選前綴的模糊Jaccard相似性連接算法,如表1所示.

表1 算法1

2.2 查詢最優(yōu)任選前綴

AS-prefixttoken(ri,j)=

基于上述分析,提出OptimalPrefixQuery(Ri)算法,如表2所示.

表2 算法2

2.3 索引最優(yōu)任選前綴

在傳統(tǒng)前綴方法中,所有的記錄按照同一個(gè)順序?qū)⒃剡M(jìn)行排序,然后選取前面固定個(gè)元素作為該記錄的前綴.其中的順序一般選擇元素的頻數(shù)升序的順序.被選擇的前綴中的元素是該記錄中頻數(shù)較低的元素.這樣做有利于減少頻數(shù)高的元素引起的大量候選.本文采用這種方法來(lái)選擇索引前綴,稱之為低頻前綴.同時(shí),選擇索引前綴時(shí)在低頻前綴的基礎(chǔ)上作了一些改進(jìn).

由于Ri的索引前綴僅用于與其后面處理的記錄的過濾,即是否與Ri+1,Ri+2,…,Rn形成候選.因此,構(gòu)造查詢前綴時(shí),考慮的不應(yīng)該是各個(gè)token在所有記錄中的頻數(shù).對(duì)于待處理記錄Ri,選擇所有未處理記錄Ri,Ri+1,Ri+2,…,Rn中各個(gè)token的低頻前綴作為索引前綴.

基于上述分析提出ImprLowFrePrefixIndex(Ri)算法,如表3所示.

表3 算法3

2.4 索引

圖1 樹的索引結(jié)構(gòu)

下面介紹在token生成候選集合時(shí)如何利用該索引結(jié)構(gòu)進(jìn)行過濾,如表4所示.

表4 算法 4

3 優(yōu) 化

3.1 生成候選的優(yōu)化

給定兩個(gè)集合A,B,若在A的某一個(gè)任意任選前綴與B的任意任選前綴中有公共token,即在A的候選集合中有B；而在另一任選前綴中與B并沒有公共token,即此時(shí)A的候選集合中并沒有B,那么此時(shí)可以斷定集合A與B并不相似.

基于此現(xiàn)象,為了減小驗(yàn)證過程所花費(fèi)的時(shí)間,可以在集合中多次選取不同任選前綴,利用不同任選前綴生成的候選的交集來(lái)縮小候選集合.然后將此發(fā)現(xiàn)應(yīng)用到二重前綴過濾算法中.

定理3設(shè)R1為任意一條記錄,C″為采用R1的任選前綴生成的候選集合,C為采用最優(yōu)任選前綴生成的候選集合,那么R1的最終候選集合為C′←C∩C″.

基于上述分析,提出了優(yōu)化生成候選算法,該算法分為三階段來(lái)完成.首先初始化候選集合C′為空集并確定任意選擇的前綴生成的候選集合C″.在每個(gè)元素中任意選擇N1個(gè)token將其加入到S1(Ri)中,隨后在S1(Ri)中任意選擇N2個(gè)子元素添加到S2(Ri)中,確定S2(Ri)中的每個(gè)子元素中的每個(gè)token生成的候選,并將候選對(duì)添加到C″中.然后確定采用最優(yōu)任選前綴生成的候選集合C.利用OptimalPrefixQuery()來(lái)生成記錄的查詢前綴,利用生成的查詢前綴以及GenCandi()來(lái)確定查詢前綴生成的候選集合C.最后取C″與C的交集.

3.2 預(yù)驗(yàn)證最大區(qū)分任選前綴

(1)

存在一個(gè)匹配,使得

(2)

存在一個(gè)匹配,邊的個(gè)數(shù)為

e≥d;

(3)

對(duì)于任意的i+j≤d-1,

(4)

由式(3)和式(4)可以推出,在二部圖中去掉任意少于等于d-1個(gè)頂點(diǎn),圖中至少還有一條邊存在.

定理4(最大區(qū)分前綴確認(rèn)) 記錄R和S的m最大區(qū)分前綴的二部圖中至少存在一條邊等價(jià)于記錄R和S的二部圖中存在一個(gè)匹配,其包含邊的個(gè)數(shù)e≥d.

由于在預(yù)驗(yàn)證階段,所有候選對(duì)的記錄的長(zhǎng)度都已知,所以d很容易求得.根據(jù)定理4可知,如果在R1與R2的d最大區(qū)分前綴的二部圖中仍有兩個(gè)頂點(diǎn)之間互相連接,那么該候選對(duì)經(jīng)過預(yù)驗(yàn)證進(jìn)入最終候選集合進(jìn)行最后驗(yàn)證.否則,R1與R2不能通過過濾器被過濾掉.

基于上述分析,本文提出了預(yù)驗(yàn)證階段最大區(qū)分任選前綴算法.首先根據(jù)求得的R1與R2中元素之間的相似值來(lái)構(gòu)建相應(yīng)的二部圖.隨后根據(jù)兩個(gè)記錄的長(zhǎng)度計(jì)算最大匹配中元素個(gè)數(shù)閾值d,并且根據(jù)閾值d來(lái)確定二部圖中需去除d-1個(gè)頂點(diǎn).然后在二部圖中去除度數(shù)最大的頂點(diǎn)以及與該頂點(diǎn)相連接的邊,每去除一個(gè)頂點(diǎn)以及相連接的邊后都需更新各頂點(diǎn)的度數(shù).此時(shí)若二部圖G中仍有兩個(gè)頂點(diǎn)之間有邊相連,那么該預(yù)候選對(duì)經(jīng)過預(yù)驗(yàn)證進(jìn)入驗(yàn)證階段.否則,該候選對(duì)被過濾掉.

4 結(jié)果與討論

所有實(shí)驗(yàn)均在具有Intel Xeon(R)CPU處理器,16 GB RAM,運(yùn)行Ubuntu 14.04.1的服務(wù)器上進(jìn)行. 所有算法均使用C ++實(shí)現(xiàn),并使用GCC 4.8.4進(jìn)行編譯.

4.1 數(shù)據(jù)集

在三個(gè)廣泛使用的數(shù)據(jù)集上來(lái)評(píng)估ASOP算法.DBLP:計(jì)算機(jī)科學(xué)出版物的數(shù)據(jù)集,其中包含題目、作者、出版商等屬性.將每個(gè)屬性看成一個(gè)元素,元素中的每個(gè)單詞看作一個(gè)token,從中隨機(jī)選擇了100萬(wàn)個(gè).QUERY LOG:搜索引擎中的查詢?nèi)罩?將每行中的單詞看成一個(gè)元素,從中隨機(jī)選擇了80萬(wàn)個(gè).WEBTABLE:大型WEB數(shù)據(jù)庫(kù),其中包含來(lái)自WEB的數(shù)百萬(wàn)個(gè)html表.本文從中隨機(jī)選擇了50萬(wàn)個(gè).具體細(xì)節(jié)如表5所示.

表5 數(shù)據(jù)集

4.2 本文算法的表現(xiàn)

用AS代表在第2節(jié)提出的基于任選前綴的相似性連接算法;ASO代表在第2節(jié)AS的基礎(chǔ)上加上生成候選的優(yōu)化算法;ASOP代表在ASO的基礎(chǔ)上對(duì)候選進(jìn)行預(yù)驗(yàn)證的過程.整個(gè)過程所需要的連接時(shí)間如圖2所示.從圖2中可以看到隨著相似性閾值τ的增長(zhǎng),三種算法的連接時(shí)間都呈下降趨勢(shì),且ASOP算法的連接時(shí)間明顯比ASO以及AS低很多.

圖2 不同數(shù)據(jù)集上所提算法的連接時(shí)間

4.3 與最先進(jìn)的算法作比較

將本文的方法與最先進(jìn)的兩種算法Silkmoth以及MF-Join作比較.在該實(shí)驗(yàn)中,固定元素級(jí)相似性閾值δ=0.8,如圖3所示.從圖中可以看出:1)不論在哪個(gè)數(shù)據(jù)集中,本文提出的ASOP算法的整體性能要遠(yuǎn)好于Silkmoth以及MF-Join; 2)在三種數(shù)據(jù)集中,MF-Join的連接時(shí)間都要比Silkmoth少; 3)在三個(gè)數(shù)據(jù)集中,ASOP的連接時(shí)間要遠(yuǎn)低于MF-Join.

接下來(lái)通過改變?cè)丶?jí)相似性閾值δ來(lái)對(duì)三種算法的連接時(shí)間進(jìn)行討論.在該實(shí)驗(yàn)中,固定相似性閾值τ=0.85,實(shí)驗(yàn)結(jié)果如圖4所示.從圖中可以看出,不論在哪個(gè)數(shù)據(jù)集中,隨著閾值δ的改變,本文算法的整體表現(xiàn)仍要好于Silkmoth和MF-Join.

圖3 改變?chǔ)拥闹蹬c當(dāng)前最先進(jìn)的方法作比較

圖4 改變?chǔ)牡闹蹬c當(dāng)前最先進(jìn)的方法作比較

5 結(jié) 語(yǔ)

本文針對(duì)相似性連接問題,提出了ASOP算法,并在三個(gè)數(shù)據(jù)集上來(lái)評(píng)估該算法.從實(shí)驗(yàn)結(jié)果中可以看出,不論是連接過程所需要的時(shí)間、或是生成的候選對(duì)的數(shù)量,本文提出的ASOP算法的效率都優(yōu)于Silkmoth以及MF-Join算法.但是由于在構(gòu)建索引部分加入了token的長(zhǎng)度以及位置信息,這就會(huì)導(dǎo)致索引所占的空間復(fù)雜度很大,今后可以在縮小索引空間上進(jìn)一步優(yōu)化.