支持增量圖數(shù)據(jù)的超圖查詢算法研究

孫勤紅

(三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京210012)

?

支持增量圖數(shù)據(jù)的超圖查詢算法研究

孫勤紅

(三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京210012)

當(dāng)前大部分圖查詢算法都是針對(duì)靜態(tài)圖數(shù)據(jù)，不適用于現(xiàn)實(shí)應(yīng)用中不斷更新的圖數(shù)據(jù)。針對(duì)這一問(wèn)題，提出支持增量圖數(shù)據(jù)的超圖查詢算法。該算法將數(shù)據(jù)圖分解成直至單個(gè)頂點(diǎn)的子圖，然后從單個(gè)頂點(diǎn)的子圖開(kāi)始求它到查詢圖的子圖同構(gòu)，直到求出數(shù)據(jù)圖到查詢圖的子圖同構(gòu)結(jié)果，算法在數(shù)據(jù)圖增加時(shí)只需將新加入的數(shù)據(jù)圖進(jìn)行分解即可，不必重新計(jì)算。通過(guò)分析證明，所提算法時(shí)間和空間復(fù)雜度不隨數(shù)據(jù)圖的增加而呈線性增長(zhǎng)，節(jié)省了大量時(shí)間和空間代價(jià)。

增量圖數(shù)據(jù);超圖查詢;算法;子圖同構(gòu)

引言

圖作為一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)被應(yīng)用到各個(gè)領(lǐng)域中，因此圖查詢[1]作為圖數(shù)據(jù)庫(kù)管理的基本工具受到越來(lái)越多的關(guān)注。

圖結(jié)構(gòu)數(shù)據(jù)的復(fù)雜性決定了圖查詢的難度。圖查詢問(wèn)題會(huì)最終轉(zhuǎn)化到子圖同構(gòu)問(wèn)題上來(lái)，所以子圖同構(gòu)是解決圖查詢問(wèn)題的關(guān)鍵。子圖同構(gòu)是NPC問(wèn)題[2]，求同構(gòu)子圖的最通用的方法是基于搜索樹(shù)的回溯。為了防止搜索樹(shù)變得過(guò)大，研究人員已提出了很多不同的優(yōu)化方法，如Ullman方法[3]、VF方法[4]以及、VF2算法[5]，另外還有利用網(wǎng)格分割方法、神經(jīng)網(wǎng)絡(luò)方法和遺傳算法等[6]。為了加快圖查詢處理過(guò)程，已有的方法大部分采用“過(guò)濾—驗(yàn)證”框架處理精確子圖查詢問(wèn)題，索引的特征有基于路徑的[7]，基于樹(shù)的[8]，還有基于子圖的[9-10]。

當(dāng)前的算法基本采用“過(guò)濾—驗(yàn)證”框架結(jié)構(gòu)，并需要對(duì)數(shù)據(jù)圖與查詢圖逐個(gè)作子圖同構(gòu)驗(yàn)證。然而，這些方法都只適用于靜態(tài)的圖查詢問(wèn)題，而不適合在不斷更新的圖數(shù)據(jù)庫(kù)上進(jìn)行圖查詢。

動(dòng)態(tài)圖數(shù)據(jù)上的圖查詢問(wèn)題面臨的難點(diǎn)有兩點(diǎn)：(1)圖數(shù)據(jù)庫(kù)是不斷變化更新的；(2)數(shù)據(jù)庫(kù)更新過(guò)程中用于回答查詢的時(shí)間有限，不能讓用戶無(wú)限制地等待。正是基于動(dòng)態(tài)圖數(shù)據(jù)的這些特點(diǎn)，現(xiàn)有的方法不適用于動(dòng)態(tài)圖查詢，除非每次更新都重新建立索引然后查詢，這樣的代價(jià)是很高的，而且更新后這些方法可能引起結(jié)果錯(cuò)誤。

基于現(xiàn)有方法的不足以及動(dòng)態(tài)圖數(shù)據(jù)頻繁更新的特點(diǎn)，本文提出了支持增量圖數(shù)據(jù)的超圖查詢方法。支持增量圖數(shù)據(jù)的超圖查詢方法的關(guān)鍵點(diǎn)在于當(dāng)數(shù)據(jù)庫(kù)增量更新后，只需將新加入數(shù)據(jù)圖分解并將結(jié)果集合加入到原有分解集合中即可，并且在分解過(guò)程中可以用到原有結(jié)果，避免重新計(jì)算，提高了增量圖數(shù)據(jù)的超圖查詢性能，節(jié)省時(shí)間和空間代價(jià)。

1 基本概念

給定圖G=(VG，EG，lGV，lGE)，g=(Vg，Eg，lgV，lgE)為G的子圖。VG和Vg分別表示圖G和子圖g中所有頂點(diǎn)的集合，EG和Eg分別表示圖G和子圖g中所有邊的集合，lGV和lgV分別表示圖G和子圖g中所有頂點(diǎn)到點(diǎn)標(biāo)簽Vc的映射函數(shù)的集合，lGE和lgE分別表示圖G和子圖g中所有邊到邊標(biāo)簽Ec的映射的集合。

定義1子圖同構(gòu)。假設(shè)S是g的子圖，如果存在一個(gè)函數(shù)f：VG→Vg，且f是從G到S的同構(gòu)，那么，稱f是從G到g的子圖同構(gòu)。

定義2圖的差。如果Vg=VG，兩者的差Gc=G-g是邊集Ec=EG-Eg；如果Vg包含于VG，兩者的差Gc=G-g是G的子圖Gc=(Vc，Ec，lcV，lcE)，其中：

(1)Vc=VG-Vg其中l(wèi)cV是Vc到點(diǎn)標(biāo)簽的映射函數(shù)；

(2)Ec=EG-Eg其中l(wèi)cE是Ec到邊標(biāo)簽的映射函數(shù)；

定義3超圖查詢。給定圖數(shù)據(jù)庫(kù)D={G1，G2，…，Gn}(n為有窮自然數(shù))和查詢圖q，找出所有的Gi滿足Gi子圖同構(gòu)于q。

定義4增量超圖查詢。給定圖數(shù)據(jù)庫(kù)D={G1，G2，…，Gn}(n為有窮自然數(shù))和查詢圖q，完成超圖查詢后數(shù)據(jù)庫(kù)D增量更新(增加數(shù)據(jù)圖)變?yōu)镈u，再次找出所有的Gi滿足Gi子圖同構(gòu)于q。

2 圖分解算法

在離線階段，將每個(gè)數(shù)據(jù)庫(kù)圖分解成子圖的集合和邊的集合。在本文中，將每個(gè)數(shù)據(jù)庫(kù)圖分解為兩個(gè)子圖，然后分別進(jìn)一步遞歸地分解兩個(gè)子圖，直到子圖是單個(gè)頂點(diǎn)的圖。

將一組數(shù)據(jù)庫(kù)圖D={G0，G1，G2，…，Gn}分解(n為有窮自然數(shù))，這里所指的分解是將每個(gè)Gi分解，得到一組由四元組構(gòu)成的有限集合DB稱為圖數(shù)據(jù)庫(kù)D的數(shù)據(jù)圖分解集合。

如果圖數(shù)據(jù)庫(kù)中的幾個(gè)圖Gi，Gj，…有公共子圖g′，或者在一個(gè)數(shù)據(jù)圖Gi中出現(xiàn)多次子圖g′，那么子圖g′成為公共子圖。在DB中用四元組表示G的分解就可以省去重新分解和計(jì)算的工作。

在已分解的DB中，最大的數(shù)據(jù)庫(kù)圖的公共子圖Smax稱為最大公共子圖。

具體的分解算法如算法1所示，算法Decomposition(D)的輸入是要被分解的數(shù)據(jù)庫(kù)圖集合D={G0，G1，G2，……，Gn}，分解后輸出元組集合用DB表示，其初值為空。

算法首先計(jì)算出數(shù)據(jù)庫(kù)D中的每個(gè)數(shù)據(jù)圖Gi的頂點(diǎn)個(gè)數(shù)，按照頂點(diǎn)個(gè)數(shù)從小到大對(duì)數(shù)據(jù)圖進(jìn)行排序，再對(duì)排序后的數(shù)據(jù)圖調(diào)用Decompose(G)將其分解。

算法用四元組集合記錄分解得到的所有子圖。子圖的個(gè)數(shù)與子圖的平均頂點(diǎn)個(gè)數(shù)成反比。如果子圖的個(gè)數(shù)增加，那么子圖的平均頂點(diǎn)個(gè)數(shù)就會(huì)減少。反之，子圖的平均頂點(diǎn)個(gè)數(shù)就會(huì)增加。為了保證子圖的平均頂點(diǎn)個(gè)數(shù)增加，算法對(duì)待處理的數(shù)據(jù)圖按頂點(diǎn)個(gè)數(shù)進(jìn)行排序，并按照頂點(diǎn)個(gè)數(shù)從小到大的順序進(jìn)行分解。當(dāng)數(shù)據(jù)圖中存在“包含”關(guān)系時(shí)，小圖首先被分解，大圖的分解也會(huì)節(jié)省代價(jià)[11]。

算法1數(shù)據(jù)圖分解算法

輸入：圖數(shù)據(jù)庫(kù)D={G1，G2，…，Gn}；

輸出：數(shù)據(jù)圖分解集合DB；

1：Decomposition(D)

2： 數(shù)據(jù)圖庫(kù)D={G1，G2，…，Gn+1}，DB=Φ；

3： 按頂點(diǎn)個(gè)數(shù)從小到大的順序?qū)中的數(shù)據(jù)圖進(jìn)行排序，得到D={Gt1，Gt2，…，Gtn+1}；

4：FORi=t1totn+1

5：Decompose(Gi)；

6：ENDFOR;

7：Decompose(Gi)

8： 設(shè)DB是已有的分解結(jié)果，Smax=Φ；

9：IF(G中只有一個(gè)頂點(diǎn))THEN

10： 返回結(jié)果；

11：ELSE調(diào)用子圖匹配算法Matchgraph(G)在已分解的tuple∈DB中求每個(gè)parent

12： 到G的子圖同構(gòu)，并找出其中的最大子圖Smax，即

13：Smax=max{parent|?∈DB∧parent是G的子圖}；

14：ENDIF

15：IF(Smax與G同構(gòu))THENEXIT；//同構(gòu)是指Smax與G的維數(shù)相同；

16：ELSEIF(Smax=NULL)THEN

17： 隨機(jī)選擇G的一個(gè)子圖Smax；

18： 求G中Smax與G-Smax之間的邊集E；

19： 將加入到DB中；

20：Decompose(Smax)；

21：Decompose(G-Smax)；

22：ELSEIF(Smax的頂點(diǎn)數(shù)=G的頂點(diǎn)數(shù)&&Smax邊數(shù)

23： 求屬于G而不屬于Smax的邊集E；

24： 從G中刪除邊集E；

25： 分解G，將tuple1加入DB中；

26：ELSE求G中Smax與G-Smax之間的邊集E；

27： 將加入到DB中；

28：Decompose(G-Smax)；

29：ENDIF

30：ENDIF

31：ENDIF

32：RETURNDB；

在分解一個(gè)數(shù)據(jù)圖G時(shí)，首先在已經(jīng)得到的子圖中查找最大的子圖Smax，然后將圖G分解為Smax和G-Smax兩部分。只有當(dāng)找不到這樣的Smax時(shí)，才將G隨機(jī)分解為兩部分。當(dāng)Smax與圖數(shù)據(jù)庫(kù)中的一個(gè)數(shù)據(jù)圖Gi的頂點(diǎn)數(shù)相同，但是Smax的邊數(shù)小于Gi的邊數(shù)時(shí)，求屬于Gi而不屬于Smax的邊集E，從Gi中刪除這些邊，并分解Gi，增加四元組。這樣既能保證子圖頂點(diǎn)個(gè)數(shù)的最大化，又能節(jié)省計(jì)算代價(jià)。

Decomposition(D)算法最重要的特點(diǎn)是對(duì)增量圖數(shù)據(jù)的分解效果明顯，圖數(shù)據(jù)庫(kù)D已經(jīng)應(yīng)用Decomposition(D)算法分解后，在D中又新增加了一個(gè)數(shù)據(jù)圖Gn+1，傳統(tǒng)的超圖查詢方法需要重新構(gòu)造索引進(jìn)行更新，而應(yīng)用Decomposition(D)算法只需執(zhí)行Decompose(Gn+1)將新加入的數(shù)據(jù)圖Gn+1分解即可，達(dá)到只對(duì)增量更新，而無(wú)需全部重新計(jì)算的特點(diǎn)。Decomposition(D)尤其適用于圖數(shù)據(jù)較大以及需要在運(yùn)行時(shí)向數(shù)據(jù)庫(kù)中新增數(shù)據(jù)圖的情況。

3 子圖的映射集合

首先采用標(biāo)準(zhǔn)測(cè)試問(wèn)題比較chaoticMOPSO與經(jīng)典的NSGA2以及當(dāng)前最新提出的BB-MOPSO兩種算法以驗(yàn)證本文所提算法的性能。

將分解得到的分解結(jié)果集DB中的單個(gè)頂點(diǎn)的子圖先與查詢圖進(jìn)行匹配，匹配成功的這些單個(gè)頂點(diǎn)的圖合并成大的子圖再與查詢圖進(jìn)行匹配，這一過(guò)程遞歸地進(jìn)行直至合并成的最后圖為圖數(shù)據(jù)庫(kù)中的數(shù)據(jù)圖本身。在此過(guò)程中會(huì)遇到兩個(gè)問(wèn)題：

(1)分解出的最小子結(jié)構(gòu)是單個(gè)頂點(diǎn)的子圖，需要有方法能夠求得單個(gè)頂點(diǎn)子圖到查詢圖的子圖同構(gòu)過(guò)程；

(2)得出分解結(jié)果集合DB且∈DB，所有這樣的元組中已求出G′和G″到查詢圖的子圖同構(gòu)，那么需要有方法將G′和G″合并成G，進(jìn)而求子圖同構(gòu)。

本文采用算法2給出的單點(diǎn)同構(gòu)檢測(cè)算法來(lái)解決問(wèn)題(1)。

算法2單點(diǎn)同構(gòu)檢測(cè)算法

//單點(diǎn)同構(gòu)檢測(cè)Vertex_Test(v，lable，GI)

輸入：分解結(jié)果DB，GI；

輸出：同構(gòu)映射集合F。

1：GI=(VGI，EGI，lGIV，lGIE)；F=Φ；lable=lGIV(v);

2：Vertex_Test(v，lable，GI)

3：FOREACHvI∈VI

4：IF(lable=lGIV(vI))THEN

5：f(v)=vI；

6：F=F∪{f}；

7：ENDIF

8：ENDFOR

9：RETURNF；

采用算法3的子圖映射組合算法MergeTuple(Tupletuple，Graphtarget)可獲得分解DB。

算法3圖映射組合算法

輸入：sub1，sub2，GI，E，F(xiàn)1，F(xiàn)2；

輸出：同構(gòu)映射集合F。

1：MergeTuple(Tupletuple，Graphtarget)

2：tuple=∈DB；

3：IF(sub2==NULL) //對(duì)于子圖sub1到target的每種可能的映射組合f1∈F1進(jìn)行如下檢查：

4：FOREACHe∈Eparent&&eEsub1，fromparentV(e)=v1，toparentV(e)=v2

5：IF(e1∈Etarget&&from

Vtarget(e1)=f1(v1) &&to

targetV(e1)=f1(v2)

6： &&arg

type

tetV(e1)=type

parentV(e))

7：f1∈F1，得到新的映射f：Vsub1→Vtarget，且f(n)=f1(n)；

8： 將f加入到parent的同構(gòu)映射表F中，即F=F∪{f}；

9：ENDIF

10：ENDFOR

11：ELSE//對(duì)于每個(gè)f1∈F1，f2∈F2進(jìn)行如下檢查：

12：IF(f1(Vsub1)∩f2(Vsub2)=Φ&& //檢查兩個(gè)子圖到target中的映射是不相交的

13： // 對(duì)于兩個(gè)子圖到target的每種可能的映射組合，判斷邊的約束：

14：FOREACHe∈Eparent&&from

parentV(e)=v1∈Vsub1&&to

parentV(e)=v2∈Vsub2

15：IF((e1∈Etarget&&from

Vtarget(e1)=f1(v1) &&to

targetV(e1)=f1(v2)

16： &&arg

type

tetV(e1)=type

parentV(e))OR

17：FOREACHe∈Eparent&&to

parentV(e)=v1∈Vsub1&&from

parentV(e) =v2∈Vsub2

18：IF((e1∈Etarget&&arg

to

Vtet(e1)=f1(v1) &&from

parentV(e1)=f1(v2)

19： &&arg

type

tetV(e1)=type

parentV(e))

20：f：Vsub1∪Vsub2→Vtarget//對(duì)于滿足a和b的每種組合合成新的映射

21： 將f加入到parent的同構(gòu)映射表F中，即F=F∪{f}；

22：ENDIF

23：ENDFOR

24：ENDIF

25：ENDIF

26：RETURNF；

對(duì)于DB中一個(gè)四元組∈DB已經(jīng)找到了所有從sub1和sub2到查詢圖的子圖同構(gòu)f1和f2，那么需要將他們組合成從parent到查詢圖的子圖同構(gòu)f，即需要判斷由f1和f2能否組合成parent到target的子圖同構(gòu)f，這一工作由MergeTuple(Tupletuple，Graphtarget)完成。該首先對(duì)sub2為空的子圖的情況進(jìn)行了分析，若sub2為空，那么只需要對(duì)屬于parent而不屬于sub1的邊進(jìn)行檢測(cè)即可。檢測(cè)包括兩部分：分別是邊的連接頂點(diǎn)類型和邊類型，對(duì)于無(wú)向圖且邊上無(wú)標(biāo)簽的圖可以將邊的類型檢測(cè)忽略；其次對(duì)sub1和sub2都不為空的情況進(jìn)行檢測(cè)，此時(shí)需要對(duì)屬于parent而不屬于sub1也不屬于sub2的邊進(jìn)行檢測(cè)，檢測(cè)的步驟同前面。

4 實(shí)驗(yàn)仿真

為了驗(yàn)證本文算法的有效性和可靠性，采用MIT地質(zhì)圖像測(cè)試數(shù)據(jù)庫(kù)為研究對(duì)象，選擇測(cè)試圖像1和測(cè)試圖像2驗(yàn)證本文算法的可擴(kuò)展性和運(yùn)行效率。對(duì)比本文算法和cIndex算法，評(píng)價(jià)指標(biāo)包括算法可擴(kuò)展性、執(zhí)行效率、離線構(gòu)造時(shí)間、索引特征的過(guò)濾能力。對(duì)比結(jié)果如圖1～圖6所示。

圖1 測(cè)試圖像1及其分解結(jié)果

圖2 測(cè)試圖像2及其分解結(jié)果

圖3 候選集大小和執(zhí)行時(shí)間

圖4 可擴(kuò)展性

圖5 離線構(gòu)造性能

圖6 閾值敏感性

由圖3可知，本文算法所需響應(yīng)時(shí)間比cIndex方法小很多，運(yùn)行效率得到了大約1個(gè)數(shù)量級(jí)的提升，主要是因?yàn)楸疚乃惴梢詫?shí)現(xiàn)數(shù)據(jù)集的壓縮，從而達(dá)到大大降低運(yùn)行計(jì)算的代價(jià)。

由圖4可知，本文算法的可擴(kuò)展性優(yōu)于cIndex方法效果較好。由圖5離線構(gòu)造性能實(shí)驗(yàn)結(jié)果可知，本文算法在執(zhí)行效率和預(yù)處理結(jié)果兩個(gè)方面均優(yōu)于cIndex方法。

由圖6可知，隨著閾值敏感性的增大，數(shù)據(jù)圖集的索引特征呈現(xiàn)下降趨勢(shì)，而執(zhí)行時(shí)間卻變長(zhǎng)，從而說(shuō)明索引特征的大小和執(zhí)行效率上存在矛盾的關(guān)系。

通過(guò)對(duì)可擴(kuò)展性、執(zhí)行效率、離線構(gòu)造時(shí)間、索引特征的過(guò)濾能力四個(gè)性能評(píng)價(jià)指標(biāo)的仿真實(shí)驗(yàn)可知，本文算法不但執(zhí)行效率高，同時(shí)也具有較低復(fù)雜度，效果較好。

5 結(jié)束語(yǔ)

本文提出了一種新的超圖查詢算法—支持增量圖數(shù)據(jù)的超圖查詢算法，該算法將數(shù)據(jù)圖分解成直至單個(gè)頂點(diǎn)的子圖，然后從單個(gè)頂點(diǎn)的子圖開(kāi)始求它到查詢圖的子圖同構(gòu)，直到求出數(shù)據(jù)圖到查詢圖的子圖同構(gòu)結(jié)果。通過(guò)文中的分析表明，相較cIndex算法，本文提出的算法對(duì)超圖的查詢更加地簡(jiǎn)單省時(shí)，同時(shí)，所提算法空間復(fù)雜度不隨數(shù)據(jù)圖的增加而呈線性增長(zhǎng)，節(jié)省了大量空間代價(jià)。

[1] Wang Xiaoli,Ding Xiaofeng,Tung A,et al.An efficient graph indexing method[C]//Proceeding of IEEE 28th International Conference on Data Engineering(ICDE),DC,Washington,April 1-5,2012:210-221.

[2] France R,Gabriel V.Chemical graphs,chemical reaction graphs,and chemical graph transformation[J].Theoretical Computer Science,2005,127(1):157-166.

[3] Moustafa W,Deshpande A,Getoor L.Ego-centric graph pattern census[C]//Proceeding of IEEE 28th International Conference on Data Engineering(ICDE),DC,Washington,April 1-5,2012:234-245.

[4] Hu Y,Wu W,Zhang B.A fast method to identify the order of frequency-dependent network equivalent[J].IEEE Transactions on Power Systems,2015,PP(99):1-9.[5] Shang Huiliang,Tao Yudong,Gao Yuan,et al.An improved invariant for matching molecular graphs based on VF2 algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(1):122-128.

[6] Perez-Ortiz M,Gutierrez P A,Hervas-Martinez C,et al.Graph-based approaches for over-sampling in the context of ordinal regression[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1233-1245.

[7] Llados J,Marti E,Villanueva J.Symbol recognition by error-tolerant sub-graph matching between region adjacency graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(10):1137-1143.

[8] Akrivi V,Michalis V,Klaus B.Algorithms and models for the Web-Graph[M].Berlin Heidelberg:Springer-Verlag,2008.

[9] Jin R,Ruan N,Dey S,et al.Scaling reachability computation on large graphs[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Arizona,May 20-24,2012:169-180.

[10] Thomsen J,Yiu M,Jensen C.Effective caching of shortest paths for location-based services[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Arizona,May 20-24,2012:313-324.

[11] 張碩,李建中,高宏,等.一種多到一子圖同構(gòu)檢測(cè)方法[J].軟件學(xué)報(bào),2010,21(3):401-414.

Research on Supergraph Query Algorithm of Support Incremental Graph Data

SUNQinhong

(School of Computer Science and Engineering, Sanjiang University, Nanjing 210012, China)

Most current graph query algorithms are applicable for static graph data, but cannot be used in constantly updated map data in real world applications. Aiming at this problem, the supergraph query algorithm of support incremental map data is put forward. The data graph is divided into subgraphs with a single vertex by using the proposed algorithm, and then from the single vertex subgraph to find it’s subgraph isomorphic to query graph, until the subgraph isomorphism results of data graph to query graph are found. When data graph increases, algorithm only needs to decomposition the newly added data graphs, and do not need to compute. The analysis shows that, the time and space complexity of proposed algorithm does not increase linearly with the increase of data graph, which saves much time and space costs.

increment map data; supergraph query; algorithm; subgraph isomorphism

2015-04-21

孫勤紅(1979-),女,山東郯城人,講師,碩士,主要從事數(shù)據(jù)挖掘方面的研究,(E-mail) 22113460@qq.com

1673-1549(2015)03-0027-06

10.11863/j.suse.2015.03.06

TP311

A