徐周波 許昌勝 王嘉鑫
摘 要:針對(duì)目前最先進(jìn)的增量子圖匹配算法Symbi中的索引結(jié)構(gòu)DCS中存在的信息冗余問題,提出了一種新的索引結(jié)構(gòu)CDCS(compressed dynamic candidate space),并提出了CDCS的更新算法INCCDCS來動(dòng)態(tài)維護(hù)CDCS索引結(jié)構(gòu)和匹配結(jié)果,最后提出了動(dòng)態(tài)圖的增量子圖匹配算法CSymbi。該方法通過引入鄰域信息約束,在構(gòu)建和更新輔助結(jié)構(gòu)的過程中過濾候選集,提高算法的求解效率。最后,在Netflow和LSBench數(shù)據(jù)集上進(jìn)行驗(yàn)證,相較于現(xiàn)有方法,候選節(jié)點(diǎn)數(shù)量最高可以刪減56%,候選邊數(shù)量最高可以刪減62%,有效縮減了計(jì)算空間并提高了算法的求解效率。
關(guān)鍵詞:動(dòng)態(tài)圖; 增量子圖匹配; 鄰域約束; CSymbi
中圖分類號(hào):TP391.4?? 文獻(xiàn)標(biāo)志碼:A?? 文章編號(hào):1001-3695(2023)12-023-3672-06
doi:10.19734/j.issn.1001-3695.2023.04.0176
Incremental subgraph matching algorithm based on neighborhood safe compression on dynamic graph
Abstract:Aiming at the problem of information redundancy in the index structure DCS in Symbi, the most advanced incremental subgraph matching algorithm, this paper proposed a new index structure CDCS, and proposed the CDCS update algorithm INCCDCS to the CDCS index structure and dynamically maintained matching results, and finally proposed an incremental subgraph matching algorithm CSymbi for dynamic graphs. By introducing neighborhood information constraints, the method filtered candidate sets during the process of constructing and updating auxiliary structures, and improved the solution efficiency of the algorithm. Finally, it was verified on the Netflow dataset and LSBench dataset. Compared with the existing methods, the number of candidate nodes can be reduced by up to 56%, and the number of candidate edges can be reduced by up to 62%, which effectively reduces the calculation space and improves the solution efficiency.
Key words:dynamic graph; incremental subgraph matching; neighborhood constraint; CSymbi
0 引言
子圖匹配是圖數(shù)據(jù)分析中一種基本操作,被廣泛應(yīng)用于社交網(wǎng)絡(luò)[1,2]、網(wǎng)絡(luò)安全[3,4]、醫(yī)學(xué)蛋白質(zhì)等領(lǐng)域[5]。子圖匹配是指在數(shù)據(jù)圖中查詢所有與查詢圖同構(gòu)的子圖。但在現(xiàn)實(shí)世界中,圖數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容往往會(huì)隨著時(shí)間的推移而發(fā)生變化。以社交網(wǎng)絡(luò)為例,根據(jù)Facebook網(wǎng)站2010年的年鑒報(bào)告,僅2010年一年期間,用戶從3.37億人增加到5.85億人,平均每分鐘都有47 553對(duì)好友之間建立或者解除關(guān)系。2011年,Google+在上線后的兩周時(shí)間增長了1 000萬的用戶[6]。這些數(shù)據(jù)表明,現(xiàn)實(shí)世界中的實(shí)體對(duì)象和他們之間的關(guān)系無時(shí)無刻都可能經(jīng)歷著變化。因此,研究動(dòng)態(tài)圖上的子圖匹配問題具有重要的理論意義和應(yīng)用價(jià)值。
增量子圖匹配技術(shù)是目前動(dòng)態(tài)圖數(shù)據(jù)匹配的主流技術(shù),其僅對(duì)動(dòng)態(tài)圖數(shù)據(jù)更新的部分進(jìn)行分析和匹配,即給定初始圖g0、查詢圖q和由邊插入和刪除(Δo1,Δo2,…)構(gòu)成的圖更新流Δg,增量子圖匹配技術(shù)針對(duì)每個(gè)更新操作Δoi給出所產(chǎn)生的正向和負(fù)向匹配結(jié)果?,F(xiàn)有的增量子圖匹配技術(shù)主要分為兩種:一種是不使用索引技術(shù),在數(shù)據(jù)圖更新后為每個(gè)受影響的子圖執(zhí)行子圖匹配算法;另一種方法則是采用索引—過濾—驗(yàn)證策略,利用索引技術(shù)對(duì)不包含q作為子圖特征的數(shù)據(jù)圖進(jìn)行過濾,然后在驗(yàn)證階段為每個(gè)候選子圖執(zhí)行子圖同構(gòu)算法。索引技術(shù)可以有效減少計(jì)算中涉及的數(shù)據(jù)圖中節(jié)點(diǎn)的數(shù)量,是現(xiàn)階段主流的研究方向之一。
IncIsoMat[7]是最早提出的增量子圖匹配算法,其首先以更新邊為中心查找該邊端點(diǎn)周圍所有k跳范圍內(nèi)的節(jié)點(diǎn),其中k為模式圖的直徑;然后計(jì)算各節(jié)點(diǎn)的導(dǎo)出子圖,并分別與模式圖進(jìn)行子圖匹配;最后查找出與原匹配結(jié)果有差異的匹配。此方法雖無須構(gòu)建索引和維護(hù)原有匹配查詢結(jié)果,但因需對(duì)k跳范圍內(nèi)的各節(jié)點(diǎn)的導(dǎo)出子圖計(jì)算子圖匹配,致使查詢效率低下。Graphflow[8]使用最壞情況最優(yōu)連接算法來增量評(píng)估每次更新的子圖匹配[9,10]。其首先從匹配更新邊(ν,ν′)的每個(gè)查詢邊(u,u′)開始,解決從部分嵌入開始的子圖匹配并遞增地連接查詢圖中的其他邊,直到它獲得查詢圖的完整嵌入集合。此方法在每次更新后都需要重新執(zhí)行子圖匹配,查詢效率低下。上述算法需要為每個(gè)更新操作執(zhí)行子圖匹配,但子圖匹配是一個(gè)NP完全問題,因此在匹配上會(huì)產(chǎn)生顯著的開銷。為提高動(dòng)態(tài)子圖匹配算法的效率,研究者們引入索引—過濾—驗(yàn)證策略,通過優(yōu)化匹配順序,或通過引入輔助數(shù)據(jù)結(jié)構(gòu)構(gòu)建索引來過濾不可行的解。文獻(xiàn)[11]提出了INC_CFLS算法,它利用分解策略對(duì)查詢圖進(jìn)行分解,將查詢圖按照節(jié)點(diǎn)度的大小分解成核心、森林和葉子三個(gè)部分。當(dāng)增加一條邊時(shí)首先確認(rèn)模式圖的影響區(qū)域,然后采用從核心到森林,最后到葉子的匹配順序,依次約減無效的中間結(jié)果?;谠擁樞蜻M(jìn)行匹配可將笛卡爾積操作拖延到葉子節(jié)點(diǎn)進(jìn)行,有效減少冗余笛卡爾積的產(chǎn)生,從而進(jìn)一步約減查詢候選集。然而,該算法僅考慮了更新節(jié)點(diǎn)對(duì)受影響區(qū)域的影響,沒有考慮更新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)對(duì)受影響區(qū)域的影響。文獻(xiàn)[12]引入了判斷更新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為影響因素條件,進(jìn)一步縮減匹配候選集和影響區(qū)域。SJTree[3]通過構(gòu)建左深度連接樹索引來提高算法的執(zhí)行效率。它將查詢圖q遞歸地分解為多個(gè)只含一條邊的子圖,每個(gè)子圖視為一個(gè)節(jié)點(diǎn),并記錄各節(jié)點(diǎn)的兄弟和父親,同時(shí)維護(hù)一個(gè)哈希表存放該節(jié)點(diǎn)的匹配結(jié)果。當(dāng)數(shù)據(jù)圖發(fā)生變化時(shí),從左深度連接樹的葉子節(jié)點(diǎn)開始向上搜索來獲取新的匹配結(jié)果,但是SJTree需要為模式圖的每條邊存儲(chǔ)部分匹配結(jié)果,致使空間復(fù)雜度為指數(shù)級(jí)。為了降低算法的空間復(fù)雜度,TurboFlux[13]借鑒了Turboiso[14]的思想,通過構(gòu)建數(shù)據(jù)中心圖(datacentric graph,DCG)來壓縮存儲(chǔ)空間,提高算法的執(zhí)行效率。它首先通過刪除循環(huán)邊將查詢圖q轉(zhuǎn)換成生成樹qt,然后通過維護(hù)一個(gè)哈希表為qt中每一條邊存放該邊的匹配結(jié)果,并通過維護(hù)一個(gè)數(shù)組來記錄兩條邊之間的嵌入關(guān)系。對(duì)于每次圖更新操作,通過判斷更新邊是否存在組成查詢圖的嵌入來獲取新的匹配結(jié)果。TurboFlux相比于SJTree,其存儲(chǔ)空間明顯減少,但在剪枝時(shí)未考慮到非樹邊,導(dǎo)致候選集存在較多冗余。Symbi算法[15]通過將查詢圖q轉(zhuǎn)換成有向無環(huán)圖來解決TurboFlux中沒有考慮非樹邊的問題。它首先通過廣度優(yōu)先搜索算法將查詢圖q轉(zhuǎn)換成有向無環(huán)圖Q,與TurboFlux類似,通過名為動(dòng)態(tài)候選空間的輔助索引結(jié)構(gòu)來維護(hù)候選節(jié)點(diǎn)集和候選邊集。有向無環(huán)圖比生成樹具有更好的修剪能力,相比于TurboFlux,過濾效果更好。在靜態(tài)圖匹配中,文獻(xiàn)[16]提出了一種新的子圖搜索算法VEQS。它也將查詢圖q轉(zhuǎn)換成有向無環(huán)圖,并將查詢圖中度為1的節(jié)點(diǎn)與其有相同標(biāo)簽的鄰居節(jié)點(diǎn)相合并,最后基于有向無環(huán)圖和過濾函數(shù)構(gòu)建緊湊的輔助索引結(jié)構(gòu),其中過濾函數(shù)利用了鄰域安全的概念,考慮了節(jié)點(diǎn)的鄰居標(biāo)簽數(shù)量約束。雖然考慮了標(biāo)簽數(shù)量約束對(duì)候選集的過濾具有良好的效果,但相比于完整的鄰域信息約束仍過于簡單。
在Symbi算法中,基于有向無環(huán)圖構(gòu)建的索引結(jié)構(gòu)能夠更好地過濾候選對(duì)象,但并未考慮利用候選節(jié)點(diǎn)的鄰域信息來進(jìn)一步篩減節(jié)點(diǎn)以及邊的候選集,導(dǎo)致候選集中存在大量無用結(jié)果,影響算法的搜索效率。鑒于此,本文將鄰域約束應(yīng)用到SymBi的DCS結(jié)構(gòu)中,給出了更加緊湊的輔助索引結(jié)構(gòu)CDCS,并提出了一種新的增量子圖匹配的算法CSymbi。通過在一些公開數(shù)據(jù)集的實(shí)驗(yàn)分析表明,本文算法與SymBi算法相比能夠有效減少輔助結(jié)構(gòu)DCS上的候選節(jié)點(diǎn)和邊集,同時(shí)因候選集的縮減,本文算法的執(zhí)行效率也有明顯提升。
1 相關(guān)定義
本文針對(duì)無向連通的節(jié)點(diǎn)屬性圖進(jìn)行研究。本文算法也可以很容易地?cái)U(kuò)展到在頂點(diǎn)或邊上有多個(gè)標(biāo)簽的有向圖。
定義1 圖。圖被定為g=(Vg,Eg,lg),其中Vg為圖g的節(jié)點(diǎn)集,Eg為圖g的邊集,lg:Vg→Σ是標(biāo)簽函數(shù),其中Σ是節(jié)點(diǎn)標(biāo)簽集。
定義2 子圖同構(gòu)。給定目標(biāo)g=(Vg,Eg,lg)和查詢圖q=(Vq,Eq,lq),如果存在單射函數(shù)f:Vq→Vg,滿足:a)u∈Vq,存在f(u)∈Vg,使得lq(u)=lg(f(u));b)u,v∈Vq,若u≠v,則f(u)≠f(v);c)(u,v)∈Eq,存在(f(u),f(v))∈Eg。則稱g的子圖sub(g)和q是子圖同構(gòu)的,并稱sub(g)為圖q的一個(gè)嵌入,表示為節(jié)點(diǎn)對(duì)(u, f(u))的集合。
例1 如圖1所示的查詢圖q和數(shù)據(jù)圖g0,其中Δo1和Δo2分別表示兩條插入邊的操作。在數(shù)據(jù)圖g0中不存在與查詢圖q同構(gòu)的子圖,執(zhí)行插入操作Δo1后數(shù)據(jù)圖更新為g1,在數(shù)據(jù)圖g1中存在2個(gè)與查詢圖q同構(gòu)的子圖,即{(u1,v1),(u2,v2),(u3,v3), (u4,v4),(u5,v5)}和{(u1,v1),(u2,v2),(u3,v3),(u4,v4),(u5,v6)}。
定義3 弱嵌入[15]。給定根節(jié)點(diǎn)u的有向無環(huán)圖Q=(VQ,EQ,lQ)和數(shù)據(jù)圖g=(Vg,Eg,lg),v∈V(g),設(shè)圖gv=(Vs,Es,lg)為圖g的包含節(jié)點(diǎn)v的節(jié)點(diǎn)集Vs的導(dǎo)出子圖,若存在單射函數(shù)M′:VQ→Vs,使得M′(u)=v,且在單射函數(shù)M′下,Q的路徑樹與gv同構(gòu),則稱M′為Q在g中v上的弱嵌入。
例2 圖1中的g0在Δo1插入后更新為g1,查詢圖q的有向無環(huán)圖Q如圖2所示。{(u3,v3),(u4,v4),(u5,v5)}是Qu3在g1中v3上的弱嵌入, 其中Qu3是Q中根節(jié)點(diǎn)u3的子圖。
定義4 圖更新流Δg。圖更新流Δg是指由一系列更新操作(Δo1,Δo2,…)組成的串。每個(gè)更新操作Δoi表示為三元組(op,v,v′),其中,op={+, -}表示更新操作的類型,“+”表示添加邊,“-”表示刪除邊,v和v′為圖g中與操作op相關(guān)的兩個(gè)節(jié)點(diǎn)。
定義5 增量子圖匹配[14]。給定初始數(shù)據(jù)圖g0、圖更新流Δg和查詢圖q,增量子圖匹配問題是為Δg中的每個(gè)更新操作找到所有正/負(fù)匹配。
2 動(dòng)態(tài)圖增量子圖匹配算法CSymbi
本文基于鄰域約束提出了一種新的增量子圖匹配算法CSymbi,算法主要分為三個(gè)步驟:a)為了保證圖的層次性及其遍歷順序的準(zhǔn)確性,利用BFS構(gòu)建查詢圖q的有向無環(huán)圖Q;b)基于有向無環(huán)圖Q和數(shù)據(jù)圖g0,針對(duì)文獻(xiàn)[15]中的DCS結(jié)構(gòu)存儲(chǔ)冗余的問題,利用鄰域信息進(jìn)行優(yōu)化,提出了一種新的輔助結(jié)構(gòu)CDCS;c)基于CDCS提出了子圖匹配的增量更新算法INCCDCS,維護(hù)CDCS結(jié)構(gòu)和匹配結(jié)果。CSymbi算法流程如算法1所示。
算法1 CSymbi
輸入:查詢圖q;數(shù)據(jù)圖g0;圖更新流Δg。
輸出:匹配結(jié)果result。
1 result←;
2 Q← BuildDAG(q);
3 CDCS←ZipDCS(Q,g0);
4 result←INCCDCS(CDCS,Q,g0,Δg)
5 return result
2.1 CDCS結(jié)構(gòu)
輔助索引結(jié)構(gòu)在增量子圖匹配中能夠有效篩選候選節(jié)點(diǎn)集,提高算法在匹配階段的速度。輔助索引結(jié)構(gòu)的設(shè)計(jì)一般從空間和時(shí)間兩個(gè)方面考慮。在空間上,希望占用盡可能小的空間的同時(shí)還能夠包含足夠多的信息;在時(shí)間上,希望索引更新足夠快,以幫助快速檢測圖模式。Symbi算法利用有向無環(huán)圖構(gòu)建DCS索引結(jié)構(gòu),并使用所有查詢邊來篩選候選節(jié)點(diǎn)集。在構(gòu)建DCS結(jié)構(gòu)時(shí),對(duì)于Q中每條邊考慮了節(jié)點(diǎn)之間的標(biāo)簽信息和邊上的標(biāo)簽信息,使用數(shù)組結(jié)合哈希表的結(jié)構(gòu)D1和D2分別存儲(chǔ)Q和Q-1兩個(gè)方向上的弱嵌入,其中 Q-1是將Q的所有邊反向后所得的圖,具體構(gòu)建過程如例3所示。
例3 對(duì)于圖1所示的查詢圖q,通過寬度優(yōu)先搜索算法轉(zhuǎn)換成如圖2所示的有向無環(huán)圖Q。然后根據(jù)Q中節(jié)點(diǎn)的標(biāo)簽信息篩選候選集,例如u2的標(biāo)簽為A,在數(shù)據(jù)圖中v2、v5、v6和v7與其具有相同的標(biāo)簽A,因此,C(u2)={v2,v5,v6,v7}。在Q中,如果存在ua到ub的邊,同時(shí)在數(shù)據(jù)圖中存在va∈C(ua)到vb∈C(ub)的邊,則將這條邊添加到DCS結(jié)構(gòu)中。例如邊(u1,u2)∈Q在DCS中需要存儲(chǔ)(v1,v2)和(v2,v1)兩條邊。因?yàn)閡2滿足Q-1u2的弱嵌入,所以D1[u2][v2]=1。但是因?yàn)镈2[u4][v4]=0,v2不滿足Q u2的弱嵌入,所以D2[u2][v2]=0。最終得到如圖3所示的初始DCS輔助結(jié)構(gòu)。
Symbi算法在構(gòu)建DCS結(jié)構(gòu)時(shí),對(duì)于Q中每條邊的候選集,僅考慮了節(jié)點(diǎn)之間的標(biāo)簽信息和邊上的標(biāo)簽信息,忽略了節(jié)點(diǎn)的鄰域信息,導(dǎo)致DCS結(jié)構(gòu)中存在冗余節(jié)點(diǎn)和冗余邊。特別是在無向圖中,這些不滿足鄰域約束,無法成為匹配結(jié)果的邊會(huì)在DCS中存儲(chǔ)2次。冗余結(jié)果既加大了輔助結(jié)構(gòu)的存儲(chǔ)空間,又?jǐn)U大了匹配階段的搜索空間,從而降低了算法的求解效率。為此,本文考慮到鄰域約束對(duì)輔助結(jié)構(gòu)的影響,在構(gòu)建和更新輔助結(jié)構(gòu)的過程中過濾候選集,優(yōu)化輔助結(jié)構(gòu)的存儲(chǔ)空間,提出了CDCS結(jié)構(gòu)。具體地,對(duì)于滿足標(biāo)簽匹配條件的候選集節(jié)點(diǎn)v∈C(u),獲取Q中節(jié)點(diǎn)u的所有父親節(jié)點(diǎn),構(gòu)成集合up。對(duì)于任一父親節(jié)點(diǎn)upi∈up,如果它的候選節(jié)點(diǎn)vpi∈C(upi)與v在數(shù)據(jù)圖存在連接關(guān)系,判斷vpi是否滿足查詢圖Q-1upi的弱嵌入條件,如果vpi不滿足,從DCS中刪除(vpi,v)。
CDCS結(jié)構(gòu)包括給定查詢圖q的有向無環(huán)圖Q和數(shù)據(jù)圖g0,CDCS由以下部分組成:
a)針對(duì)u∈V(q),候選集C(u)是一組滿足lq(u)=lg(v)的頂點(diǎn)集合,其中v∈V(g0)。
b)對(duì)于任意u∈V(q)和v∈C(u),如果在節(jié)點(diǎn)v處存在Q-1u的弱嵌入,D1[u,v]=1;否則D1[u,v]=0。
c)對(duì)于任意u∈V(q)和v∈C(u),如果在節(jié)點(diǎn)v處存在Qu的弱嵌入M′,并且對(duì)于M′中的每個(gè)映射(u′,v′)都滿足D1[u′,v′]=1,則D2[u,v]=1;否則D2[u,v]=0。
d)當(dāng)(u,u′)∈E(q),(v,v′)∈E(g),且滿足D1[u,v]=1、D1[u′,v′]=1時(shí),則在〈u,v〉和〈u′,v′〉之間存在一條邊(〈u,v〉,〈u′,v′〉)。
CDCS的構(gòu)建如算法2所示。算法2中,第1行表示構(gòu)建基于Q的DCS輔助結(jié)構(gòu);第2~6行為獲取存儲(chǔ)在DCS中的候選集,其中g(shù)etCandid函數(shù)用于獲取節(jié)點(diǎn)up到節(jié)點(diǎn)u的候選集;第5、6行為判斷節(jié)點(diǎn)v的父親節(jié)點(diǎn)vp是否滿足Q-1up弱嵌入條件,Remove函數(shù)對(duì)于不滿足的邊從DCS中移除;第7行返回輔助索引結(jié)構(gòu)CDCS。
算法2 ZipDCS
輸入:有向無環(huán)圖Q;數(shù)據(jù)圖g0。
輸出:輔助結(jié)構(gòu)CDCS。
1 DCS←BuildDCS(g0,Q);
2 for each u in Q.NumVertices
3? ?for each up in u.Parents
4??? ?for each [vp,v] in getCandid(DCS,up,u)
5????? ?if D1[up, vp]=0 then
6???????? CDCS←remove(DCS,vp,v);
7 return CDCS
例4 D1[u][v]=0表示節(jié)點(diǎn)v不滿足Q-1u的弱嵌入關(guān)系,所以將把v作為起始節(jié)點(diǎn)或者終節(jié)點(diǎn)的特征邊從DCS結(jié)構(gòu)中刪除。例如邊(v7,v3),因?yàn)関7不滿足Q-1u2的弱嵌入,D1[u2][v7]=0,所以(v7,v3)這條邊被刪除,同時(shí)(v3,v7)也會(huì)被刪除。圖3中所有不滿足鄰域約束的邊用紅色標(biāo)注(見電子版),將所有不滿足約束條件的邊刪除后,結(jié)果如圖4所示。
從圖3和4的對(duì)比可以看出,經(jīng)過壓縮后,相比于DCS結(jié)構(gòu),CDCS結(jié)構(gòu)所包含的邊集數(shù)量減少了50%。這是因?yàn)镃DCS結(jié)構(gòu)在構(gòu)建過程中將鄰域約束加入到了輔助結(jié)構(gòu)的構(gòu)建過程中,減少不符合匹配條件的候選集,從而達(dá)到了壓縮邊集的目的。相比之下,DCS結(jié)構(gòu)只考慮了節(jié)點(diǎn)之間的標(biāo)簽信息和邊上的標(biāo)簽信息,沒有考慮鄰域信息,導(dǎo)致結(jié)構(gòu)中存在大量冗余邊,浪費(fèi)了存儲(chǔ)空間。
2.2 CDCS更新
當(dāng)數(shù)據(jù)圖中的邊發(fā)生更新時(shí),CDCS中將插入或刪除一組邊,下面分別對(duì)插入邊和刪除邊的更新操作進(jìn)行介紹。
a)邊插入。DCS針對(duì)插入邊e(vp,v),如果D1[up][vp]=0,則邊e(vp,v)的插入不影響D1及其后代的更新,因此不會(huì)產(chǎn)生新的匹配結(jié)果,停止更新并移動(dòng)到下一條邊的判斷;如果D1[up][vp]=1,則(u,v)及其后代的D1可能因?yàn)閑(vp,v)的插入發(fā)生改變而產(chǎn)生新的匹配結(jié)果。首先更新(u,v)及其后代的D1信息,如果D1[u][v]=1,將e(vp,v)插入到CDCS結(jié)構(gòu)中(針對(duì)無向圖),然后繼續(xù)向下判斷后代節(jié)點(diǎn),直至D1不滿足為1終止。針對(duì)邊插入的CDCS結(jié)構(gòu)的更新操作如算法3所示。
算法3的DCS第1行為初始化隊(duì)列;第2行獲取更新邊;第3行InsertToDataGraph函數(shù)更新數(shù)據(jù)圖;第4行將邊的起始節(jié)點(diǎn)添加到隊(duì)列中;第5~13行依次從隊(duì)列中取出節(jié)點(diǎn),遞歸更新D1;其中第8行g(shù)etChild函數(shù)獲?。╱,v)的孩子節(jié)點(diǎn)集(uc_candid,vc_candid);第9行遍歷節(jié)點(diǎn)集,依次更新節(jié)點(diǎn)(uc,vc)∈(uc_candid,vc_candid)的D1;第12行CDCSInsertUpdate函數(shù)獲取uc的父親節(jié)點(diǎn)up∈Q,針對(duì)up的候選集,如果D1[up][vp]=1且(vp,v)∈Eg,則將(vp,v)和(v,vp)存儲(chǔ)到CDCS中;第14行UpdateD2函數(shù)更新D2;第15行UpdateMathches函數(shù)根據(jù)已更新的D1和D2尋找新的匹配,并更新匹配結(jié)果;第16行返回匹配結(jié)果result。
算法3 CDCSInsert
輸入:輔助結(jié)構(gòu)CDCS;有向無環(huán)圖Q;數(shù)據(jù)圖g;圖更新操作Δo。
輸出:匹配結(jié)果result。
1 queue←;
2 e(v,vc)←(Δo.v,Δo.vc);
3 InsertToDataGraph(g,e);
4 queue.add([u,v]);
5 while (!queue.isEmpty())
6 [u,v]←queue.pop();
7 if (D1[u][v]==1)then
8?? (uc_candid,vc_candid)←getChild((u,v));
9?? for each(uc,vc)∈(uc_candid,vc_candid)
10??? update D1(uc,vc);
11??? if (D1[uc][vc]==1) then
12???? CDCSInsertUpdate(CDCS,Q,v,vc);
13???? queue.add([uc,vc]);
14 update D2(u,uc,v,vc);
15 result←UpdateMathches(e);
16 return result
b)邊刪除。DCS針對(duì)刪除邊e(vp,v),首先更新匹配結(jié)果,然后將其從數(shù)據(jù)圖和CDCS結(jié)構(gòu)中刪除。接著更新(u,v)及其后代的D1信息。如果某些節(jié)點(diǎn) D1由1變?yōu)?,同時(shí)指向該節(jié)點(diǎn)的邊存在于CDCS中,將其從CDCS中移除。針對(duì)邊刪除的CDCS結(jié)構(gòu)的更新操作如算法4所示。
算法4 CDCSDelete
輸入:輔助結(jié)構(gòu)CDCS;有向無環(huán)圖Q;數(shù)據(jù)圖g;圖更新操作Δo。
輸出:匹配結(jié)果result。
1 queue←;
2 e(v,vc)←(Δo.v,Δo.vc);
3 result←UpdateMathches(e);
4 DeleteFromDataGraph(g,e);
5 queue.add([uc,vc]);
6 while (!queue.isEmpty())
7 [u,v]←queue.pop();
8 CDCSDelUpdate(CDCS,Q,v,vc);
9 (uc_candid,vc_candid)←getChild((u,v));
10 for each (uc,vc)∈(uc_candid,vc_candid)
11? update D1(uc,vc);
12? if (D1[uc][vc]==0) then
13??? queue.add([uc,vc]);
14 update D2(u,uc,v,vc);
15 return result
例5 圖5(a)(b)分別是圖1(b)中Δo1和Δo2更新后的結(jié)果。Δo1={+,v3,v4}插入數(shù)據(jù)圖g0后,首先從隊(duì)列中獲取節(jié)點(diǎn)對(duì)(u3,v3)。因D1[u3][v3]=1,重新計(jì)算(u3,v3)的孩子節(jié)點(diǎn)(u4,v4),(u5,v5),(u5,v6),(u5,v7)的D1。因?yàn)閡4的每一個(gè)父親節(jié)點(diǎn)都有一個(gè)與v4相鄰的候選集,其D1的值為1,所以D1[u4][v4]由0變?yōu)?,將(u4,v4)存儲(chǔ)到隊(duì)列中,然后獲取u4在Q中的父親節(jié)點(diǎn)u2和u3。因D1[u2][v2]=1和D1[u3][v3]=1,所以將(v2,v4),(v4,v2),(v3,v4)和(v4,v3)插入到CDCS中。繼續(xù)從隊(duì)列中獲?。╱4,v4),因?yàn)樵摴?jié)點(diǎn)無孩子節(jié)點(diǎn)且隊(duì)列為空,更新結(jié)束。D1更新結(jié)束后繼續(xù)更新D2,因D1[u4][v4]=1,且滿足Qu4的弱嵌入,所以D2[u4][v4]=1,繼續(xù)向上更新,最終得到{(u1,v1),(u2,v2),(u3,v3),(u4,v4),(u1,v1),(u5,v5)}和{(u1,v1), (u2,v2),(u3,v3),(u4,v4),(u1,v1),(u5,v6)}兩個(gè)匹配結(jié)果。同理當(dāng)Δo2={+,v1,v7}插入時(shí),CDCS結(jié)構(gòu)如圖5(b)所示。
基于此,CDCS結(jié)構(gòu)的更新算法INCCDCS如算法5所示。以輔助結(jié)構(gòu)CDCS,有向無環(huán)圖Q,數(shù)據(jù)圖g0和圖更新流Δg為輸入,更新CDCS并返回匹配結(jié)果。
算法5 INCCDCS
輸入:輔助結(jié)構(gòu)CDCS;有向無環(huán)圖Q;數(shù)據(jù)圖g;圖更新流 Δg。
輸出:匹配結(jié)果result。
1 result←;
2 for each Δo∈Δg
3 ?if (Δo.op=+) then
4?? result←CDCSInsert(CDCS,Q,g,Δo);
5 ?if (Δo.op=-) then
6?? result←CDCSDelete(CDCS,Q,g,Δo);
7 return result
3 實(shí)驗(yàn)
為證明本文算法CSymbi的有效性,使用公開數(shù)據(jù)集Netflow和LSBench數(shù)據(jù)集與Symbi算法進(jìn)行實(shí)驗(yàn)對(duì)比,其中Symbi源碼從文獻(xiàn)[17]中獲取。實(shí)驗(yàn)是在一臺(tái)Corei56500@3.2 GHz、16 GB內(nèi)存的機(jī)器上進(jìn)行的,源碼使用C語言進(jìn)行編寫,運(yùn)行在 CentOS Linux操作系統(tǒng)上。
LSBench是由鏈接流基準(zhǔn)數(shù)據(jù)生成器生成的合成RDF社交媒體流數(shù)據(jù),包含23 317 563個(gè)三元組。Netflow是一個(gè)真實(shí)的數(shù)據(jù)集,包含從CAIDA獲得的匿名被動(dòng)流量追蹤,約包含18 520 759個(gè)三元組??紤]到內(nèi)存限制,從數(shù)據(jù)集中選取0.1的三元組,約2 000 000的三元組作為實(shí)驗(yàn)數(shù)據(jù)。默認(rèn)情況下將數(shù)據(jù)集的90%三元組分成初始圖,10%分成圖更新流。查詢圖參照文獻(xiàn)[13,15],通過從數(shù)據(jù)圖中隨機(jī)提取子圖來生成查詢圖。其中查詢圖的類型分為樹型圖T和循環(huán)圖G兩種。對(duì)于每種類型,將查詢圖的節(jié)點(diǎn)數(shù)量以3的增量從6增長到12,例如T6表示樹型圖節(jié)點(diǎn)數(shù)量為6,G12表示循環(huán)圖節(jié)點(diǎn)數(shù)量為12。為每種大小和類型的查詢圖生成了100個(gè)實(shí)例作為一個(gè)查詢集。實(shí)驗(yàn)過程中將本文的CSymbi和Symbi算法進(jìn)行對(duì)比,將輔助結(jié)構(gòu)包含的候選集大小、更新過程中的平均運(yùn)行時(shí)間、程序的平均峰值內(nèi)存使用情況以及解決的查詢圖數(shù)量作為算法之間的衡量標(biāo)準(zhǔn),其中峰值內(nèi)存定義為實(shí)際程序輸出中虛擬集大小的最大值。
首先,在Netflow數(shù)據(jù)集上對(duì)比每次更新操作中DCS和CDCS包含的平均節(jié)點(diǎn)數(shù)和平均邊數(shù)。實(shí)驗(yàn)數(shù)據(jù)是在數(shù)據(jù)圖不變的情況下,不同類型和大小的查詢圖q的100個(gè)實(shí)例運(yùn)行的平均結(jié)果。按照模式圖的規(guī)模將實(shí)驗(yàn)分成了六組,實(shí)驗(yàn)結(jié)果如表1所示。其中DCS|V|表示DCS中包含的平均節(jié)點(diǎn)數(shù)量,DCS|E|表示DCS中包含的平均邊的數(shù)量,CDCS類似。而R|V|和R|E|分別表示相比于DCS,CDCS中節(jié)點(diǎn)數(shù)量和邊數(shù)量減少的比例。從表1中可以看出,CSymbi算法的候選集大小始終小于Symbi算法,從縮減比例中可以看出,相比于原算法,本文算法對(duì)候選節(jié)點(diǎn)的過濾最高可以達(dá)到56%,對(duì)候選邊集的過濾最高可以達(dá)到54%。同樣在LSBench中進(jìn)行相同的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表2所示,其中節(jié)點(diǎn)數(shù)量最多降低49%,而邊集數(shù)量則可以降低62%。從實(shí)驗(yàn)結(jié)果可見,加入鄰域約束對(duì)輔助結(jié)構(gòu)中候選集的過濾有明顯優(yōu)勢。
其次,分別在Netflow和LSBench上對(duì)比了本文算法與Symbi在插入邊時(shí)算法的平均耗時(shí)。實(shí)驗(yàn)過程中插入率為10%,實(shí)驗(yàn)結(jié)果如圖6(a)和(b)所示。從實(shí)驗(yàn)結(jié)果可以看出,在兩個(gè)數(shù)據(jù)集的六組實(shí)驗(yàn)上,CSymbi算法的平均耗時(shí)均優(yōu)于Symbi算法。這是因?yàn)楹蜻x集數(shù)量的減少將會(huì)縮減算法在匹配階段的搜索空間,能夠提高算法在匹配階段的求解效率。在實(shí)驗(yàn)過程中,發(fā)現(xiàn)在個(gè)別的查詢實(shí)例下,CSymbi比Symbi慢,主要原因是Symbi在初始化DCS結(jié)構(gòu)時(shí)會(huì)將所有標(biāo)簽匹配的節(jié)點(diǎn)和邊使用哈希表進(jìn)行存儲(chǔ),在數(shù)據(jù)圖發(fā)生變化時(shí),通過DCS查找候選集;但CSymbi刪除了不滿足鄰域約束的邊集和節(jié)點(diǎn),在后續(xù)更新中需要從原數(shù)據(jù)圖中查找可能滿足匹配的新節(jié)點(diǎn)和邊,所以在某些實(shí)例中速度較慢。但從整體實(shí)驗(yàn)的平均結(jié)果中可以看出,CSymbi始終優(yōu)于Symbi。
然后,為了驗(yàn)證算法在運(yùn)行過程中實(shí)際所占用的內(nèi)存大小,將兩個(gè)算法在運(yùn)行過程中所占的峰值內(nèi)存大小進(jìn)行了實(shí)驗(yàn)對(duì)比。圖7(a)和(b)顯示了在Netflow和LSBench上執(zhí)行增量子圖匹配的平均峰值內(nèi)存。從實(shí)驗(yàn)結(jié)果可以看出,在不同查詢圖規(guī)模下,CSymbi使用的內(nèi)存都明顯少于SymBi。原因是CSymbi算法中各候選集在CDCS輔助結(jié)構(gòu)中存儲(chǔ),不論是節(jié)點(diǎn)集還是邊集,相較于Symbi都有明顯減少。
進(jìn)一步,在相同的實(shí)驗(yàn)環(huán)境下對(duì)比了執(zhí)行刪除操作時(shí)兩個(gè)算法的平均查詢時(shí)間和平均峰值內(nèi)存。刪除率設(shè)置為10%。實(shí)驗(yàn)結(jié)果如圖8和9所示。在執(zhí)行刪除操作時(shí),Symbi和CSymbi算法在刪除邊時(shí)同樣會(huì)將要?jiǎng)h除的邊從輔助結(jié)構(gòu)中移除,但是CSymbi在更新受影響節(jié)點(diǎn)的D1時(shí)會(huì)判斷值是否由1變?yōu)?,如果變?yōu)?,會(huì)將其從候選集中移除,因此在內(nèi)存上同樣優(yōu)于Symbi算法。
最后對(duì)比了Turboflux、Symbi和CSymbi算法在解決查詢圖數(shù)量上的性能差異。本文將算法的運(yùn)行時(shí)間設(shè)置為1 h,統(tǒng)計(jì)不同算法在規(guī)定時(shí)間內(nèi)所能解決的查詢圖數(shù)量,實(shí)驗(yàn)結(jié)果如圖10所示。從圖中可以看出,Turboflux算法在規(guī)定時(shí)間有較多查詢不能解決,而Symbi和CSymbi算法能夠解決大部分的查詢,但隨著查詢圖規(guī)模的增大,Symbi算法在個(gè)別查詢圖上無法得出結(jié)果。主要原因在于部分查詢圖的候選集數(shù)量過于龐大,在執(zhí)行更新操作時(shí),搜索速度過慢,導(dǎo)致算法的求解效率降低,無法在規(guī)定時(shí)間內(nèi)得到結(jié)果。
4 結(jié)束語
為了進(jìn)一步壓縮增量子圖匹配問題的求解空間,本文提出了一種基于鄰域約束的增量子圖匹配算法CSymbi。該算法考慮節(jié)點(diǎn)周圍的鄰居約束關(guān)系,對(duì)輔助索引結(jié)構(gòu)DCS的候選集作進(jìn)一步篩選,壓縮輔助結(jié)構(gòu)的存儲(chǔ)空間,提出了CDCS索引結(jié)構(gòu),同時(shí)提出輔助索引結(jié)構(gòu)CDCS的更新算法,對(duì)CDCS及其匹配結(jié)果進(jìn)行更新。實(shí)驗(yàn)結(jié)果表明,該算法與Symbi算法相比較,有效地壓縮了輔助索引結(jié)構(gòu)的存儲(chǔ)空間,同時(shí)因?yàn)楹蜻x集的減少,更新過程明顯加快。在未來的工作中,將研究輔助索引結(jié)構(gòu)的符號(hào)壓縮技術(shù),并結(jié)合增量算法對(duì)其進(jìn)行求解。
參考文獻(xiàn):
[1]于靜,劉燕兵,張宇,等.大規(guī)模圖數(shù)據(jù)匹配技術(shù)綜述[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):391-409.(Yu Jing, Liu Yanbing, Zhang Yu, et al. A survey of largescale graph data matching technology[J].Computer Research and Development,2015,52(2):391-409.)
[2]Zou Lei, Chen Lei, zsu M T. Distancejoin:pattern match query in a large graph database[J].Proceedings of the VLDB Endowment,2009,2(1):886-897.
[3]Choudhury S, Holder L, Chin G, et al. A selectivity based approach to continuous pattern detection in streaming graphs[J].Computer Science,2015,93(8):939-945.
[4]Gao Jun, Zhou Chang, Yu J X. Toward continuous pattern detection over evolving large graph with snapshot isolation[J].The VLDB Journal,2016,25:269-290.
[5]He Huahai, Singh A K. Query language and access methods for graph databases[M]//Managing and Mining Graph Data.2010:125-160.
[6]許嘉,張千楨,趙翔,等.動(dòng)態(tài)圖模式匹配技術(shù)綜述[J].軟件學(xué)報(bào),2018,29(3):663-688.(Xu Jia, Zhang Qianzhen, Zhao Xiang, et al. A survey of dynamic graph pattern matching technology[J].Journal of Software,2018,29(3):663-688.)
[7]Fan Wenfei, Wang Xin, Wu Yinghui. Incremental graph pattern matching[J].ACM Trans on Database Systems,2013,38(3):1-47.
[8]Kankanamge C, Sahu S, Mhedbhi A, et al. Graphflow: an active graph database[C]//Proc of the 44th ACM International Conference on Management of Data.New York:ACM Press,2017:1695-1698.
[9]Mhedhbi A, Salihoglu S. Optimizing subgraph queries by combining binary and worstcase optimal joins[J].Proceedings of the VLDB Endowment,2019,12(11):1692-1704.
[10]Ngo H Q, Ré C, Rudra A. Skew strikes back: new developments in the theory of join algorithms[J].ACM SIGMOD Record,2014,42(4):5-16.
[11]許嘉,張千楨,趙翔,等.基于結(jié)構(gòu)分解的動(dòng)態(tài)圖增量匹配算法[J].計(jì)算機(jī)科學(xué)與探索,2018,12(8):1214-1224.(Xu Jia, Zhang Qianzhen, Zhao Xiang, et al. Dynamic graph incremental matching algorithm based on structural decomposition[J].Computer Science and Exploration,2018,12(8):1214-1224.)
[12]張芳.基于增量的動(dòng)態(tài)圖匹配算法研究[D].秦皇島:燕山大學(xué),2021.(Zhang Fang. Research on dynamic graph matching algorithm based on increment[D].Qinhuangdao:Yanshan University,2021.)
[13]Kim K, Seo I, Han W S, et al. TurboFlux: a fast continuous subgraph matching system for streaming graph data[C]//Proc of the 6th International Conference on Management of Data.New York:ACM Press,2018:411-426.
[14]Han W S, Lee J, Lee J H. TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases[C]//Proc of ACM SIGMOD International Conference on Management.New York:ACM Press,2013:337-348.
[15]Min S, Park S G, Park K, et al. Symmetric continuous subgraph matching with bidirectional dynamic programming[J].Proceedings of the VLDB Endowment,2021,14(8):1298-1310.
[16]Kim H, Choi Y, Park K, et al. Versatile equivalences:speeding up subgraph query processing and subgraph matching[C]//Proc of the 4th International Conference on Management of Data.New York:ACM Press,2021:925-937.
[17]Sun Xibo, Sun Shixuan, Luo Qiong, et al. An indepth study of continuous subgraph matching[J].Proceedings of the VLDB Endowment,2022,15(7):1403-141.