基于坐標(biāo)映射及多重圖劃分的圖相似查詢研究

劉哲峰,梁 平,顧進(jìn)廣

(1.武漢科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430065;2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室,湖北 武漢 430065)

0 引 言

隨著信息技術(shù)的迅速發(fā)展,所獲得的數(shù)據(jù)呈爆炸式增加。根據(jù)國際數(shù)據(jù)公司(IDC)的統(tǒng)計,互聯(lián)網(wǎng)上的數(shù)據(jù)每年將增長50%以上,而且世界上90%以上的數(shù)據(jù)是最近幾年產(chǎn)生的[1]。這些數(shù)據(jù)中,容量巨大、結(jié)構(gòu)復(fù)雜、種類繁多而且語義多變的數(shù)據(jù)占據(jù)了很大比例[2-3]。

總體而言,在數(shù)據(jù)及數(shù)據(jù)間的關(guān)系飛速增長的時代,圖數(shù)據(jù)庫被應(yīng)用到越來越多的領(lǐng)域,如機(jī)電電力[4-5]、醫(yī)學(xué)信息[6]、信用卡欺詐檢測[7]等。而圖形的激增也激發(fā)了人們對在大型圖數(shù)據(jù)庫中實現(xiàn)高效訪問功能和靈活的結(jié)構(gòu)感知查詢的興趣[8]。關(guān)于圖數(shù)據(jù)庫的查詢方式,有檢索條件約束[9]以及查詢結(jié)果約束兩大類,而基于查詢結(jié)果約束,已經(jīng)出現(xiàn)了許多相關(guān)的研究,它們可以大致分為兩類:圖精確搜索[10-11]和圖相似性搜索[12-13]。與精確搜索相比,相似性搜索可以提供一種魯棒的解決方案,允許容錯并支持搜索未精確定義的模式。

兩個標(biāo)記圖之間的相似性計算是圖相似性搜索的核心操作,目前最主要的相似性度量為:圖編輯距離[13-14]、最大公共子圖[15-16]、圖對齊[17]和圖核函數(shù)[18-19]。該文考慮基于圖編輯距離(GED)約束定義的相似性搜索問題,主要是因為其通用性和廣泛的適用性[20],GED是一種幾乎適用于任何類型的圖形的度量。直觀的圖編輯操作可以精確捕捉與圖形結(jié)構(gòu)和內(nèi)容相關(guān)的任何細(xì)粒度差異[21]。典型的編輯操作[22]是插入和刪除頂點或邊以及重新標(biāo)記頂點或邊。

該文研究了以下圖相似性搜索問題:給定一個圖數(shù)據(jù)庫G={g1,g2,…,gn}和一個查詢圖q,需要找到圖G中的所有圖g,使其相對于查詢圖q的圖編輯距離GED(g,q)在用戶指定的閾值τ內(nèi)。

然而,GED的計算是NP-hard,因此計算所有查詢圖q和g∈G的GED可能會導(dǎo)致較差的計算效率。現(xiàn)有的解決方案大多采用過濾驗證框架來加快圖形的相似性搜索。在過濾階段,通過種種算法相對快速地評估出一個GED下界,它被用于從圖數(shù)據(jù)庫中修剪盡可能多的假陽性圖,剩下的圖構(gòu)成候選集C。在驗證階段,必須在q和每個候選圖之間執(zhí)行GED計算來驗證。

到目前為止,已經(jīng)提出了不同的GED下界[13,21,23-24],這些技術(shù)具有一些缺點:(1)對于圖數(shù)據(jù)庫G中的所有數(shù)據(jù)圖進(jìn)行GED下界的評估,沒有考慮到圖規(guī)模的差距,會導(dǎo)致很多無意義的GED下界計算;(2)過于寬松的GED下界并沒有保證其過濾能力,導(dǎo)致很多假陽性圖無法識別;(3)GED下界評估耗時,會帶來較高的驗證成本。

該文考慮了一種基于坐標(biāo)映射的多重圖劃分方法。首先,將圖數(shù)據(jù)庫以及查詢圖進(jìn)行坐標(biāo)系的映射,并以此為基礎(chǔ)構(gòu)建坐標(biāo)系上的查詢矩形對圖數(shù)據(jù)庫中不符合條件的圖進(jìn)行粗粒度過濾,以降低后續(xù)圖劃分的計算成本。這種過濾方式十分快速,但是并不精密;然后,使用基于參數(shù)的圖劃分的選擇性計算方法有效地控制圖劃分的隨機(jī)性,并基于該方法得到有效的GED下界,來提升過濾精度;最后,通過不同的劃分方式以及參數(shù)控制構(gòu)建不同的索引集,以實現(xiàn)多層索引過濾,更進(jìn)一步提升過濾的精度。

1 問題定義

1.1 圖與相似查詢

該文采用的圖均為簡單的、無向的標(biāo)記圖。圖g定義為一個四元組(Vg,Eg,lg,Σ),其中Vg是頂點集;Eg?Vg×Vg是邊集;lg:Vg∪Eg→Σ是一個標(biāo)簽函數(shù),其中Σ是頂點和邊的標(biāo)簽集。

圖g可以被執(zhí)行的圖編輯操作為:(1)刪除一條邊;(2)在兩個頂點間插入一條邊;(3)修改一條邊的標(biāo)簽;(4)刪除一個孤立的頂點;(5)插入一個孤立的頂點;(6)修改一個頂點的標(biāo)簽。

定義1(相似查詢):給定一個圖數(shù)據(jù)庫G={g1,g2,…,gn},一個查詢圖q和一個GED閾值τ,相似查詢的問題是找到一個數(shù)據(jù)圖gi∈G,使得GED(gi,q)≤τ。

1.2 半邊圖與圖劃分

定義2(半邊圖):半邊圖g=(Vg,Eg,lg,Σ),其中,Eg?Vg×(Vg∪{*})是一個可能存在半邊(u,*)∈Eg的圖,其中一個關(guān)聯(lián)頂點u∈Vg是一個確定的頂點,但該半邊的另一個頂點(及其標(biāo)號)沒有明確的指定,表示為*。

定義3(圖劃分):圖g可以劃分為集合窮舉、互斥和非空半邊圖的集合p,如下所示:

P(g)={pi|∪iVpi=Vg'∪iEpi?Eg∪Vg×{*},pi∩pj=?,?i,j≠j}

其中,P被稱為g的一個劃分。

將圖劃分為半邊子圖對GED有一個明顯的優(yōu)勢,就是在給定任何圖編輯操作的情況下,它最多只能影響一個半邊圖的劃分。

2 基于坐標(biāo)映射的多重圖劃分

2.1 坐標(biāo)映射

在現(xiàn)實的圖數(shù)據(jù)庫中,圖的規(guī)模均有較大的差異,而在圖編輯操作中,對于頂點和邊的刪除或增加均是從圖規(guī)模上進(jìn)行操作?；谶@一點,設(shè)計了一個坐標(biāo)映射的批量過濾方法。

對于任一數(shù)據(jù)圖g,將其以坐標(biāo)(|Vg|,|Eg|),也就是基于頂點-邊的方式,映射于二維坐標(biāo)系中,其中,x坐標(biāo)和y坐標(biāo)分別代表圖g的頂點數(shù)和邊數(shù)。因此,對于圖數(shù)據(jù)庫G,可以獲得點集{(|Vg|,|Eg|):g∈G},而這些點可以組成一個矩形區(qū)域A=[xmin,xmax]×[ymin,ymax],其中xmin/xmax和ymin/ymax分別是節(jié)點和邊的最小數(shù)量和最大數(shù)量。

定義4(查詢矩形):給定一個查詢圖q和閾值τ,查詢矩形Aq被定義為由點集{(x,y):|x-|Vq‖+|y-|Eq‖≤τ}組成的矩形。

對于一個數(shù)據(jù)圖g,如果GED(g,q)≤τ,那么必定會有:‖Vg|-|Vq‖+‖Eg|-|Eq‖≤τ。由此可以在矩形區(qū)域A中進(jìn)行圖規(guī)模上的批量過濾,圈定出如圖1所示的查詢矩形Aq。

圖1 圖數(shù)據(jù)庫的坐標(biāo)矩形A和查詢矩形Aq

坐標(biāo)映射的著眼點在于圖的大小,考慮的是一種邊界情況,這有助于從圖規(guī)模上剔除了那些不符合要求的圖,是一種粗粒度的過濾手段,以減少后續(xù)精細(xì)過濾的時間開銷。因此,經(jīng)過這坐標(biāo)映射這一層的粗粒度過濾之后,所需要參與后續(xù)多重圖劃分的細(xì)粒度過濾的數(shù)據(jù)圖數(shù)量明顯減少,能顯著加快后續(xù)細(xì)粒度過濾方法的索引構(gòu)建時間。

算法1給出了坐標(biāo)映射方法的算法描述。首先,初始化坐標(biāo)矩形A的最大值和最小值(行1);然后,對于圖數(shù)據(jù)庫中的每個圖,計算其頂點數(shù)和邊數(shù)并更新A的最大值和最小值(行2～6),并將其坐標(biāo)存儲到坐標(biāo)矩形A中(行7);接著,使用查詢圖的頂點數(shù)和邊數(shù)計算查詢矩形Aq,并找到與查詢圖相似的圖的坐標(biāo)(行9～11);最后,返回坐標(biāo)矩形A和查詢矩形Aq(行12)。

算法1:坐標(biāo)映射方法

輸入:圖數(shù)據(jù)庫G; 閾值τ;查詢圖q;

輸出:坐標(biāo)矩形A和查詢矩形Aq

1→xmin=infinity,xmax=-infinity,ymin=infinity,ymax=-infinity;

2→for eachginGdo

3→····if |Vg|

4→····if |Vg|>xmaxthenxmax=|Vg|;

5→····if |Eg|

6→····if |Eg| >ymaxthenymax=|Eg|;

7→····A.add((|Vg|, |Eg|));

8→Aq= set();

9→for eachginGdo

10→··if abs(|Vg|-|Vq|) + abs(|Eg|-|Eq|) ≤τthen

11→······Aq.add((|Vg|, |Eg|))

12→returnA,Aq

2.2 參數(shù)化的GED下界

由1.2中的定義3,可以推導(dǎo)出如下定理:

定理1:給定一個圖g,該圖被劃分為(τ+k)個半邊圖,該半邊圖的集合為P(g),其中τ為閾值,k(k≥1)是一個整數(shù)參數(shù)。對于給定的查詢圖q,如果GED(g,q)≤τ,則在半邊圖集合P(g)中至少存在k個半邊圖:pi1,pi2,…,pik∈P(g),滿足pil?q(1≤l≤k)。

對于任意數(shù)據(jù)圖g∈G,其分區(qū)集合為P(g)={p1,p2,…,pτ+k},如果pi?q,則稱pi為匹配分區(qū),否則稱其為不匹配分區(qū)。根據(jù)定理1,如果分區(qū)集合P中的匹配分區(qū)數(shù)小于k,則圖編輯距離GED(g,q)必然是大于τ的,由此可判斷出g是一個假陽性圖,大大節(jié)約了時間成本。同時,為了更好地了解圖劃分方法的使用,給出了例子1進(jìn)行說明。

例子1 對于圖2中的數(shù)據(jù)圖g1以及查詢圖q,假設(shè)閾值τ=2。令整數(shù)參數(shù)k=2,那么g1需要劃分出四個半邊圖。對于圖g1的劃分P(g1)如圖2所示。因為P(g1)相對于圖q來說有三個不匹配分區(qū):p1,p2和p4。因此g1是一個假陽性圖。

圖2 g1的四個半邊圖:P(g1)={p1,p2,p3,p4}

定理1提供了一個參數(shù)化的,基于分區(qū)的GED下界,通過設(shè)置不同的k值,就可以生成一系列新的GED下界。同時當(dāng)k取不同的值時,新生成的GED下界的過濾能力也具有了一定的差異。當(dāng)k=1時,實例化的GED下界歸結(jié)為一個特殊的降級情況。對于給定的一個假陽性圖g∈G,它的(τ+1)個分區(qū),可以很容易地找到1個(k=1)匹配分區(qū),一旦找到,g將被錯誤的納入候選圖中,然而當(dāng)k>1時,g作為假陽性圖將更有可能被識別和過濾,因為從g中檢測k>1個匹配分區(qū)的可能性要遠(yuǎn)小于k=1時。

因此,k>1時,它比k=1這種退化情況更有可能識別出假陽性圖。當(dāng)k>1時,GED下界可以實例化為一系列更緊密的下界,對相似性搜索具有更好的過濾能力。

2.3 選擇性圖劃分

對于給定的任意一個數(shù)據(jù)圖來說,可以有很多種劃分方法,能將其劃分為(τ+k)個不同大小和結(jié)構(gòu)分區(qū)。因此如果不加以限制,圖劃分方法會充滿隨機(jī)性,針對這種情況同樣給出了例子2進(jìn)行說明。

例子2 同樣是圖2中的數(shù)據(jù)圖g1,如果采用圖3的劃分方式,P1(g1)中,p2和p3均為匹配分區(qū),此時數(shù)據(jù)圖g1會通過篩選。

圖3 g1的四個半邊圖:P1(g1)={p1,p2,p3,p4}

為了對這種隨機(jī)劃分方式進(jìn)行限制,為每個分區(qū)賦予了一個如式1所示的選擇性增益s(pi),它表明如果g是假陽性圖,pi作為不匹配分區(qū)pi?q的選擇性有多高,其中f()是圖數(shù)據(jù)庫G中的頂點/邊的標(biāo)簽頻率。為此,對于數(shù)據(jù)圖的最優(yōu)劃分的目標(biāo)是將數(shù)據(jù)圖劃分為具有最高總體選擇值的(τ+k)個分區(qū)。

(1)

式中,s(pi)的值受兩個因素的影響:

(1)分區(qū)大小:較大的分區(qū)更有可能受圖編輯距離的影響,從而使得該分區(qū)成為不匹配分區(qū)的概率更大;

(2)頂點/邊標(biāo)簽的頻率:在查詢圖q中,標(biāo)簽頻率在G中較小的分區(qū)可能按比例很少出現(xiàn)。因此,包含低頻率頂點/邊的分區(qū)更有可能是不匹配分區(qū)。

選擇性劃分的算法如算法2所示。對于輸入的數(shù)據(jù)圖g,首先創(chuàng)建一個布爾數(shù)組M,它表示是否將頂點v分配給某個分區(qū),并將M初始化為false(行1);同時初始化另一個集合Una,它保存即將處理的數(shù)據(jù)圖g的未分配頂點,初始化為空(行2);接下來選擇τ+k個頂點,以此作為τ+k個分區(qū)的初始頂點,同時這些頂點的相鄰且未被分配的頂點N(·)添加到Una中,這些存放在Una中的頂點將在下一步中考慮用于分區(qū)分配(行3～8);接著通過評估將每個頂點v分配給每個現(xiàn)有分區(qū)pi的選擇性增益(由式1計算)來檢查每個未分配的頂點,使得每個頂點分配到該分區(qū)后具有最大的選擇性增益,并將頂點v的相鄰且未被分配的頂點添加到Una中(行9～15);在所有頂點都分配完成后,就需要開始考慮跨區(qū)的邊,并將它們作為半邊分配給其中一個參與分區(qū),同樣需要計算所分配半邊的選擇性增益(行16～22)。這樣通過貪心算法,將每一個除了初始化頂點以外的頂點和跨分區(qū)的邊進(jìn)行選擇性增益的計算,最終返回相對最優(yōu)的分區(qū)集合。

算法2:選擇性圖劃分

輸入:數(shù)據(jù)圖g,閾值τ,參數(shù)k,查詢圖q

輸出:圖劃分P(g)={p1,p2,…,pτ+k}

1→for eachv∈VgdoM[v]=false;

2→Una = ?*, /*Una為未分配頂點集合*/

3→fori=1 toτ+kdo

4→····for onev∈VgandM[v]== false

5→········pi={v};

6→········M[v]= true;

7→········for eachu∈N(v),M[u]==false andu? Una

8→············Una = Una∪{u};

9→for eachv∈Una

10→··fori=1 toτ+kdo

11→······ei=s(pi∪{v})-s(pi);

13→··M[v]=true;

14→··for eachu∈N(v),M[u]==false andu? Una

15→······Una = Una∪{u};

16→for each (u,v)∈Eg,uandv∈pi,i≠j

17→··ei=s(pi∪(u, *))-s(pi);

18→··ej=s(pi∪(v, *))-s(pi);

19→··ifei≥ejthen

20→······pi=pi∪{(u, *)};

21→··else

22→······pi=pi∪{(v, *)};

23→returnP(g)={p1,p2,…,pτ+k}

頂點和邊標(biāo)簽的頻率可以在構(gòu)建坐標(biāo)矩形階段進(jìn)行一次預(yù)計算,因此,該算法的時間復(fù)雜度為O((τ+k)|Vg|+|Eg|)。

2.4 標(biāo)簽頻率表與倒排索引

上述的選擇性圖劃分方式給原本的隨機(jī)劃分提供了一個約束,使得不穩(wěn)定的隨機(jī)劃分變的更加可控。然而半邊子圖的匹配算法同樣具有很高的代價,因此為了進(jìn)一步降低半邊子圖匹配的驗證成本,可以構(gòu)建以下兩個表進(jìn)行進(jìn)一步過濾:

(1)標(biāo)簽頻率表:為分區(qū)p構(gòu)造一個標(biāo)簽頻率表R(p),其中存儲分區(qū)p的頂點和邊標(biāo)簽的頻率。在執(zhí)行半邊子圖同構(gòu)的計算之前,首先比較它們的頻率表R(p)和R(q):對于R(p)中每個頂點/邊標(biāo)簽的頻率不應(yīng)該超過R(q),記為R(p)≤R(q),這樣可以節(jié)省半邊子圖同構(gòu)的計算代價;

(2)倒排索引:為圖g的一個劃分p構(gòu)建一個倒排索引I(p)。對于給定的查詢圖q,如果p?q,可以在圖數(shù)據(jù)庫G中快速找到包含劃分p的所有數(shù)據(jù)圖。這樣,在進(jìn)行完必要的劃分p的半邊子圖同構(gòu)計算后,可以通過倒排索引找到所有包含劃分p的數(shù)據(jù)圖,以此減少大量的計算。

通過構(gòu)建與維護(hù)上述兩個表單,將子半邊子圖匹配的過程同樣劃分為過濾-驗證兩個部分,以進(jìn)一步壓縮計算成本。

2.5 多層索引

雖然可以基于上訴方法選擇一個緊湊的、基于劃分的GED下界,并利用選擇性劃分的方法產(chǎn)生相對優(yōu)秀的半邊子圖,然而可能仍然有一些假陽性圖未被識別。因此選擇采用多層索引結(jié)構(gòu)來對圖數(shù)據(jù)庫進(jìn)行過濾。

為了充分利用多個GED下界,采用集中過濾策略,考慮了L種不同的圖劃分方法,P1,P2,…,PL,其中Pi將g∈G劃分為(τ+ki)個分區(qū)。具體來說,在第i層,評估由ki參數(shù)化的第i個GED下界,并生成候選圖Ci,并由該候選圖Ci繼續(xù)進(jìn)行下一層的過濾,當(dāng)且僅當(dāng)通過了所有層的GED下界評估之后,才能得到最終的候選集C。

為了保證索引分區(qū)和GED下界約束能在多層索引結(jié)構(gòu)的不同層之間顯著變化,考慮了以下策略:

(1)在不同層應(yīng)用選擇性分區(qū)方法時,從數(shù)據(jù)圖g中隨機(jī)選擇初始節(jié)點;

(2)在不同層間選擇不同的參數(shù)ki的值。

這樣可以使用相同的選擇性分區(qū)方法,通過不同的初始節(jié)點和不同的參數(shù)ki,保證每層索引都能產(chǎn)生不同的分區(qū)索引集,以此為GED下界提供嚴(yán)密性保證。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境

為了檢測該算法的效率與準(zhǔn)確性,將與Pars算法[23]進(jìn)行對比實驗。Pars算法是采用單個降級GED下界(k=1)和隨機(jī)劃分進(jìn)行索引生成和相似性搜索的圖索引方法,相較于其他的算法具有更好的效率,Pars算法所采用的半邊子圖同構(gòu)算法與文中算法均為A*算法。同時為了體現(xiàn)坐標(biāo)映射所帶來的性能提升,將對文中算法以及Pars算法進(jìn)行有無坐標(biāo)映射的對比實驗。

而對于文中算法,為了體現(xiàn)出在2.5節(jié)中提出的多層索引結(jié)構(gòu)的過濾層數(shù)對算法的影響,實驗中選取雙層索引結(jié)構(gòu)和三層索引結(jié)構(gòu)進(jìn)行對比。

隨機(jī)從NCI/NIH數(shù)據(jù)集中選擇10 000個圖作為數(shù)據(jù)集,并從中隨機(jī)選擇一個圖作為查詢圖。

在實驗中主要考慮了以下性能評估指標(biāo):

(1)索引構(gòu)建成本:包括參與索引算法的圖數(shù)量、索引構(gòu)建時間;

(2)候選圖數(shù)量:即在進(jìn)行過濾之后所產(chǎn)生的候選圖數(shù)量;

(3)查詢執(zhí)行時間:相似性搜索的真實響應(yīng)時間,是候選集生成時間及GED驗證時間之和,同樣這里的時間是多次實驗后平均的響應(yīng)時間。

實驗運行環(huán)境如下:Window11操作系統(tǒng)、16 GB內(nèi)存的Core i7-11800H 2.30 GHz 8核電腦;Pars算法和文中算法均采用C++編程語言實現(xiàn),編譯環(huán)境為Microsoft Visual Studio 2022。

3.2 實驗結(jié)果分析

3.2.1 索引構(gòu)建成本

首先,在圖數(shù)據(jù)庫中評估不同方法的索引構(gòu)建成本。值得注意的是,圖索引是離線預(yù)構(gòu)建的,對于圖數(shù)據(jù)庫G,考慮GED閾值τ是很小的(τ≤4),其主要原因是用戶會更傾向于從圖數(shù)據(jù)庫中搜索相似的圖。

表1為在不同閾值τ下,無坐標(biāo)映射和有坐標(biāo)映射時,參與索引構(gòu)建的數(shù)據(jù)圖數(shù)量。從表1可知,有坐標(biāo)映射時,會過濾掉相當(dāng)一大批從圖的規(guī)模上就不符合要求的數(shù)據(jù)圖,從而大大減輕了索引的構(gòu)建負(fù)擔(dān)。同樣,當(dāng)閾值越大時,說明用戶對相似度的要求越松,通過坐標(biāo)映射的數(shù)據(jù)圖數(shù)量也會大幅度上升,但是哪怕閾值τ已經(jīng)為6了,它仍然能過濾掉近2/3的數(shù)據(jù)圖。

表1 有無坐標(biāo)映射時參與索引構(gòu)建的圖數(shù)量

圖4表示在無坐標(biāo)映射時Pars算法、采用雙層索引及采用三層索引的文中算法的時間開銷?？梢钥吹娇梢杂行?gòu)建多層索引。同樣,因為需要構(gòu)建多層索引,以及需要選擇較好的圖劃分,多層索引在構(gòu)建時間上略長于Pars算法的單層隨機(jī)劃分的索引。而隨著閾值τ的增加,這種索引構(gòu)建時間的差距開始變的微不足道,這是因為當(dāng)τ變得更大時,每個數(shù)據(jù)圖會相應(yīng)地被劃分為更大數(shù)量的更小分區(qū),從而導(dǎo)致半邊子圖同構(gòu)計算加速,而半邊子圖同構(gòu)的計算時間通常會占用總索引構(gòu)建時間的90%以上。

圖4 無坐標(biāo)映射的索引構(gòu)建時間

表2給出了在AIDS中不同閾值、無標(biāo)簽頻率表及倒排索引表的情況下,半邊子圖同構(gòu)所需要的時間。之所以排除標(biāo)簽頻率表和倒排索引表的干擾,是因為這兩者很大程度上會受到圖劃分的影響,若是采用隨機(jī)劃分方法,那么在不排除標(biāo)簽頻率表和倒排索引表的情況下,半邊子圖同構(gòu)時間會變的相對隨機(jī),若是采用文中的選擇性劃分方法,那么半邊子圖同構(gòu)時間的影響因子又會變的過多。從表2可以看出,隨著閾值的增大,半邊子圖同構(gòu)的時間會被加速。

表2 半邊子圖同構(gòu)時間

圖5表示在有坐標(biāo)映射時,Pars算法、采用雙層索引和采用三層索引的文中算法的索引構(gòu)建時間對比。從圖5可知,其與圖4變化趨勢不同:隨著閾值τ增大,索引構(gòu)建的時間整體呈上升趨勢。結(jié)合表1可以發(fā)現(xiàn),當(dāng)閾值τ增大時,表明對查詢圖的相似性要求越來越低,通過坐標(biāo)映射的圖的數(shù)量顯然會越來越多,這就導(dǎo)致了參與索引構(gòu)建的圖的數(shù)量上升,因此在閾值變大的情況下,哪怕有著半邊子圖同構(gòu)的計算加速,參與計算的圖數(shù)量顯然影響更大。

圖5 有坐標(biāo)映射的索引構(gòu)建時間

3.2.2 候選圖數(shù)量

其次,比較了不同方法所產(chǎn)生的候選圖數(shù)量。圖6表示Pars算法、采用雙層索引及采用三層索引的文中算法所產(chǎn)生的候選圖數(shù)量,其中Real表示實際的相似圖數(shù)量。從圖中可以看出,文中所采用的算法,其過濾出的候選圖始終小于Pars,哪怕是雙層索引結(jié)構(gòu)都能比Pars算法減少近45%的假陽性圖。原因有兩個:首先,參數(shù)k>1的廣義GED下界比降級(k=1)的更緊密;其次,選擇性分區(qū)方法比Pars中的隨機(jī)分區(qū)更有效地生成高選擇性的索引分區(qū),這有助于更進(jìn)一步地過濾假陽性圖。另外,可以看到當(dāng)索引層數(shù)增多,被過濾掉的假陽性圖也顯著增加,這表明多層索引方法具有更出色的過濾能力,與Pars的單層隨機(jī)劃分的方法相比,可以保證假陽性圖數(shù)量的減少。

圖6 候選圖數(shù)量

3.2.3 查詢執(zhí)行時間

最后,評估了Pars算法、采用雙層索引及采用三層索引的文中算法的總體運行的時間成本。因為評估的是最終的候選圖及GED驗證的時間,故而有無坐標(biāo)映射對該部分幾乎是沒有影響的。評估結(jié)果如圖7所示。可以發(fā)現(xiàn),相比于隨機(jī)劃分的單層過濾方法Pars,文中的多層索引的過濾效果要更好,因為坐標(biāo)軸是按指數(shù)增加的,所以就算看起來沒有增加多少,但實際上是差距越來越大的,這主要是因為多層索引所生成的候選集明顯更少,這樣總體運行時間才會更少,說明選擇性圖劃分方法的多層索引結(jié)構(gòu)明顯具有更好的,更精確的過濾效果。

圖7 查詢執(zhí)行時間

綜合上述的實驗結(jié)果可以得出以下結(jié)論:首先,基于坐標(biāo)映射的預(yù)過濾方法可以有效減少參與后續(xù)細(xì)粒度過濾方法的數(shù)據(jù)圖數(shù)量,從而明顯減少細(xì)粒度過濾方法的索引構(gòu)建時間;其次,雖然在索引構(gòu)建階段,文中算法因為需要對分區(qū)質(zhì)量進(jìn)行調(diào)整,所以整體索引構(gòu)建時間要略長于隨機(jī)劃分的Pars算法,但是圖6和圖7的實驗結(jié)果表明,其過濾性能與精度是要明顯優(yōu)于Pars算法的,從整體的查詢速度來看,文中算法的整體查詢速度是要明顯優(yōu)于Pars算法的。

4 結(jié)束語

相似性搜索問題在管理和查詢圖結(jié)構(gòu)數(shù)據(jù)中起著最基本的和最關(guān)鍵的作用,并且在現(xiàn)實世界中大規(guī)模的圖數(shù)據(jù)庫中有廣泛的應(yīng)用。該文探討了在圖編輯距離的約束下的相似性搜索問題,并在Pars算法的基礎(chǔ)上進(jìn)一步引入多層索引結(jié)構(gòu)來解決圖相似性搜索這一問題,同時針對多層索引結(jié)構(gòu)的構(gòu)建時間開銷過大的問題,提出了坐標(biāo)映射的批量圖處理方式來有效減少過濾階段的時間成本。首先采用坐標(biāo)映射來過濾掉一大批從規(guī)模上就超出相似度閾值的圖,然后使用參數(shù)化的、選擇性圖劃分方式的GED下界來過濾假陽性圖,以此使得圖劃分變得更加可控,同時通過倒排索引和標(biāo)簽頻率表來減少子圖同構(gòu)的時間開銷,最終通過生成多個索引集來對批量過濾后的圖再次進(jìn)行交叉檢查,以此提升過濾的精度。這樣,在保證多層索引過濾精度的同時,使用坐標(biāo)映射大大減少了時間成本。模擬實驗結(jié)果證明,坐標(biāo)映射提升了算法的時間性能,而多層索引的引入提升了算法過濾的精度。