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

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

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

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