精確子圖數據庫查詢技術研究.pdf

1、圖是一種通用的數據結構，相比路徑和樹結構來說，圖能表達更多復雜的結構信息，如：分子結構、社交網絡關系、圖像。近年來，隨著圖數據在各個應用領域內被廣泛使用，其數據量成指數級迅速積累，導致對這些海量數據的管理成為一項重要的研究工作。圖數據管理中重要的分支之一是子圖查詢技術研究。圖查詢技術具有自己的特點與難點：1、數據結構相對其他較復雜，操縱困難。2、子圖同構問題在精確子圖查詢過程中是不可避免的，而且已被證明是NP難問題。3、圖數據種類繁雜。

2、為了解決這一系列的問題，使得圖查詢技術的研究充滿了挑戰(zhàn)與機遇。
　　本文針對圖數據庫中的精確子圖查詢技術，主要完成了以下工作：
　?。?）根據現有頻繁子圖挖掘算法，選取高效的頻繁子圖挖掘算法作為本論文的離線挖掘算法。通過對AGM、FSG、gSpan算法的對比，得出基于深度挖掘的gSpan算法的通用性與高效性，相比基于寬度優(yōu)先挖掘的算法來說：1、使用DFS碼對圖進行編碼，避免了匹配過程中的子圖同構問題。2、避免了Apriori

3、逐層擴展產生的大量中間結果帶來的計算開銷。
　?。?）結合頻繁模式特征挖掘算法，提出一種新的基于頻繁子圖中鄰接邊哈希索引構建方法AG-Index：利用過濾-驗證模型，對頻繁圖部分構建索引存入緩存內，非頻繁部分放在磁盤，得到候選項后用現有效率較高的子圖同構算法進行驗證。實驗證明，AG-Index比經典高效的gIndex和FG-Index算法過濾能力更強，內存占有率更小，并在AG-Index的基礎上對其進行了更進一步的優(yōu)化，實驗證明，