支持動(dòng)態(tài)圖數(shù)據(jù)的圖查詢算法研究.pdf

1、圖作為一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)被應(yīng)用到各個(gè)領(lǐng)域中，如分子化學(xué)和社會(huì)網(wǎng)絡(luò)領(lǐng)域，圖查詢作為圖數(shù)據(jù)庫(kù)管理的一項(xiàng)重要課題在近些年來(lái)受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。圖查詢問題是在圖數(shù)據(jù)庫(kù)中找到滿足條件的數(shù)據(jù)圖集合，其中分為子圖查詢和超圖查詢。隨著數(shù)據(jù)量的日益增加，圖查詢?cè)跒橛脩籼峁└鼜?qiáng)大更全面的功能的同時(shí)也使得查詢處理過程及索引構(gòu)建更加復(fù)雜。如何高效地支持靜態(tài)圖數(shù)據(jù)和動(dòng)態(tài)圖數(shù)據(jù)上的圖查詢問題至關(guān)重要。
　　目前，已經(jīng)有許多工作致力于解決圖查詢問題。其中

2、大部分工作采用“過濾—驗(yàn)證”框架處理圖查詢問題，主要集中精力于建立索引等數(shù)據(jù)結(jié)構(gòu)來(lái)提前過濾掉部分非結(jié)果集，再將查詢圖與候選集合中的圖逐個(gè)做子圖同構(gòu)檢測(cè)，最終得到結(jié)果集合?，F(xiàn)有解決圖查詢問題的方法大致分為基于特征過濾和不基于特征過濾的，這些方法都是基于靜態(tài)圖數(shù)據(jù)的，而在現(xiàn)實(shí)應(yīng)用中大部分圖數(shù)據(jù)是頻繁更新的，現(xiàn)有方法對(duì)于動(dòng)態(tài)圖數(shù)據(jù)上的圖查詢問題代價(jià)較高。圖查詢問題本身就是NPC問題，在動(dòng)態(tài)圖數(shù)據(jù)上圖查詢問題就變得更加困難。
　　針對(duì)上述

3、問題本文提出了支持動(dòng)態(tài)圖數(shù)據(jù)的子圖查詢方法和支持增量圖數(shù)據(jù)的超圖查詢方法。支持動(dòng)態(tài)圖數(shù)據(jù)的子圖查詢方法首先構(gòu)造出每張圖的拓?fù)鋵哟涡蛄凶鳛樗饕?，再根?jù)序列間的匹配關(guān)系過濾出候選集合，最后用圖同構(gòu)算法驗(yàn)證候選集中的圖最終得到結(jié)果集合。該方法的索引構(gòu)造簡(jiǎn)單且體積小，在圖數(shù)據(jù)庫(kù)更新后無(wú)需重構(gòu)索引，不僅支持動(dòng)態(tài)圖數(shù)據(jù)上的子圖查詢，在靜態(tài)圖數(shù)據(jù)上也表現(xiàn)出良好的性能。支持增量圖數(shù)據(jù)的超圖查詢方法基于“分治法”思想，將數(shù)據(jù)圖分解成直至單個(gè)頂點(diǎn)的子圖，然