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

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

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

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