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

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

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

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