基于結構分解的動態圖增量匹配算法*

許 嘉，張千楨，趙 翔，呂 品，李陶深,2

1.廣西大學 計算機與電子信息學院，南寧 530004

2.廣西高校并行分布計算技術重點實驗室，南寧 530004

3.廣西多媒體通信與網絡技術重點實驗室，南寧 530004

4.國防科技大學 信息系統與管理學院，長沙 410073

1 引言

隨著信息科技與互聯網的快速發展，數據規模不斷增長，數據類型不斷增多，不同領域關注的實體對象之間的關系變得更加復雜，如何分析和挖掘大數據中蘊含的復雜關系吸引了諸多研究學者。圖（graph）作為一種廣泛使用的數據結構，圖中的每個節點代表現實世界中的實體對象，節點之間的邊表示實體之間的關系，適合描述上述這種存在有內在復雜關系的數據。子圖模式匹配返回數據圖中所有和給定模式圖相同或相似的子圖，是分析和挖掘圖數據的重要查詢操作，具有眾多實際應用。例如在社交網絡（新浪微博、微信等）中，子圖模式匹配通常用于挖掘目標客戶團體[1]；又如在生物分析領域中，子圖模式匹配可用于對未知性質的蛋白質進行輔助分析[2]。

然而在現實世界中，描述實體對象圖數據的結構和內容往往會隨著時間的推移發生變化。例如社交網絡中，2010年Facebook網站的用戶從3.37億人增加到5.85億人，平均每分鐘都會有47 553對好友之間建立或者解除關系；2011年，Google+在上線后的兩周時間增長了1 000萬的用戶[3]。生物分析領域中，蛋白質與酶會發生復雜的交互與代謝關系，導致蛋白質的結構發生變化。這些數據表明，現實世界中的實體對象和它們之間的關系無時無刻都可能經歷著變化。……