孫勤紅

(三江學院計算機科學與工程學院, 南京210012)

?

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

孫勤紅

(三江學院計算機科學與工程學院, 南京210012)

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

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

引言

圖作為一種復雜的數(shù)據(jù)結構被應用到各個領域中，因此圖查詢[1]作為圖數(shù)據(jù)庫管理的基本工具受到越來越多的關注。

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

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

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

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

1 基本概念

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

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

定義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到點標簽的映射函數(shù)；

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

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

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

2 圖分解算法

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

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

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

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

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

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

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

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

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

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

1：Decomposition(D)

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

3： 按頂點個數(shù)從小到大的順序將D中的數(shù)據(jù)圖進行排序，得到D={Gt1，Gt2，…，Gtn+1}；

4：FORi=t1totn+1

5：Decompose(Gi)；

6：ENDFOR;

7：Decompose(Gi)

8： 設DB是已有的分解結果，Smax=Φ；

9：IF(G中只有一個頂點)THEN

10： 返回結果；

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

12： 到G的子圖同構，并找出其中的最大子圖Smax，即

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

14：ENDIF

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

16：ELSEIF(Smax=NULL)THEN

17： 隨機選擇G的一個子圖Smax；

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

19： 將加入到DB中；

20：Decompose(Smax)；

21：Decompose(G-Smax)；

22：ELSEIF(Smax的頂點數(shù)=G的頂點數(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；

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

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

3 子圖的映射集合

首先采用標準測試問題比較chaoticMOPSO與經典的NSGA2以及當前最新提出的BB-MOPSO兩種算法以驗證本文所提算法的性能。

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

(1)分解出的最小子結構是單個頂點的子圖，需要有方法能夠求得單個頂點子圖到查詢圖的子圖同構過程；

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

本文采用算法2給出的單點同構檢測算法來解決問題(1)。

算法2單點同構檢測算法

//單點同構檢測Vertex_Test(v，lable，GI)

輸入：分解結果DB，GI；

輸出：同構映射集合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；

輸出：同構映射集合F。

1：MergeTuple(Tupletuple，Graphtarget)

2：tuple=∈DB；

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

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的同構映射表F中，即F=F∪{f}；

9：ENDIF

10：ENDFOR

11：ELSE//對于每個f1∈F1，f2∈F2進行如下檢查：

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

13： // 對于兩個子圖到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//對于滿足a和b的每種組合合成新的映射

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

22：ENDIF

23：ENDFOR

24：ENDIF

25：ENDIF

26：RETURNF；

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

4 實驗仿真

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

圖1 測試圖像1及其分解結果

圖2 測試圖像2及其分解結果

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

圖4 可擴展性

圖5 離線構造性能

圖6 閾值敏感性

由圖3可知，本文算法所需響應時間比cIndex方法小很多，運行效率得到了大約1個數(shù)量級的提升，主要是因為本文算法可以實現(xiàn)數(shù)據(jù)集的壓縮，從而達到大大降低運行計算的代價。

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

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

通過對可擴展性、執(zhí)行效率、離線構造時間、索引特征的過濾能力四個性能評價指標的仿真實驗可知，本文算法不但執(zhí)行效率高，同時也具有較低復雜度，效果較好。

5 結束語

本文提出了一種新的超圖查詢算法—支持增量圖數(shù)據(jù)的超圖查詢算法，該算法將數(shù)據(jù)圖分解成直至單個頂點的子圖，然后從單個頂點的子圖開始求它到查詢圖的子圖同構，直到求出數(shù)據(jù)圖到查詢圖的子圖同構結果。通過文中的分析表明，相較cIndex算法，本文提出的算法對超圖的查詢更加地簡單省時，同時，所提算法空間復雜度不隨數(shù)據(jù)圖的增加而呈線性增長，節(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] 張碩,李建中,高宏,等.一種多到一子圖同構檢測方法[J].軟件學報,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