圖數據庫中的子圖查詢算法研.pdf

1、圖是計算機科學中的重要數據結構。隨著信息技術地不斷發(fā)展，出現了越來越多的以圖作為邏輯表達的數據，例如化學分子結構式，生物網絡，社會網絡以及圖像中的實體關系等等。另一方面，這些圖數據本身的數據量也在不斷增大，例如每天就有4,000個新的化學結構被加入到SCF Finder數據庫；現在的社會網絡圖中的結點數目超過了1 億5 千萬。如何有效地管理和挖掘海量的圖數據是圖數據庫研究的核心問題。具體包括：1如何建立有效的存儲機制和索引策略；2如何有

2、效地回答圖數據庫中的查詢；3如何從海量的圖數據庫中挖掘出有用的信息。
　　 子圖查詢是圖數據管理中的基本操作。具體地說，給定一個查詢圖Q 在圖數據庫中找到所有包含查詢圖Q的數據圖。由于子圖同構是典型的NP 完全問題，目前的子圖查詢算法均采用“過濾-精化”的算法來找到結果集。在過濾階段，根據某種子圖同構的必要條件過濾掉不可能包含查詢圖Q的數據圖；然后在精化階段利用子圖同構算法在剩下的數據圖中找到結果集。目前的大部分的過濾策略都是基

3、于“特征子結構”獴敲汩湧簡稱“特征”捵牲敮捹的方法。這種方法沒有考慮到特征之間的拓撲關系。根據特征和特征之間的拓撲關系，設計一種新的過濾策略將加快子圖查詢的響應時間。另外目前的子圖查詢算法沒有考慮數據庫頻繁動態(tài)更新的情況。
　　 當數據庫出現增刪改時，不得不重新建立索引。為了適應動態(tài)的圖數據庫，根據圖譜理論，將圖的拓撲信息映射到數據空間中；并根據映射的數值空間，建立相應的索引結構。這種方法不但加快了過濾的時間，且可以動態(tài)的維護索

4、引結構。
　　 隨著社會網絡等復雜網絡的出現，給定查詢圖Q 如何在一張大圖中找到Q的匹配位置是非常有意義的課題，例如可以幫助我們找到社會網絡中的特定的朋友圈，以及生物網絡中的功能團。大圖上的匹配的定義本身并一定是基于子圖同構。因為網絡上考慮的更多的是兩點之間的連接性關系。根據連接性關系，找到查詢圖Q的所有匹配位置。因為通常復雜網絡中的節(jié)點數目是海量的，為了減少搜索空間，將圖結構中映射到向量空間。通過在向量空間的操作，找到所有的候

5、選匹配位置；然后在原來的圖結構中確定最終的匹配結果集。
　　 圖數據挖掘可以幫助我們從海量的圖數據中找到有用的知識，其中頻繁結構模式挖掘和結構相關性挖掘是兩個重要的課題。目前的結構模式挖掘算法大部分采用“生成-檢測”的算法框架。這種方法的缺點是“檢測”階段耗費大量時間。根據圖數據的特例“樹數據”的特點，采用模式增長的方式設計頻繁結構模式挖掘算法，從避免了檢測階段。給定一個查詢圖Q 希望從圖數據庫中找到與Q有高度相關性的子結構。這