圖數(shù)據(jù)庫中的子圖查詢算法研.pdf

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

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

3、于“特征子結(jié)構(gòu)”獴敲汩湧簡稱“特征”捵牲敮捹的方法。這種方法沒有考慮到特征之間的拓?fù)潢P(guān)系。根據(jù)特征和特征之間的拓?fù)潢P(guān)系，設(shè)計(jì)一種新的過濾策略將加快子圖查詢的響應(yīng)時(shí)間。另外目前的子圖查詢算法沒有考慮數(shù)據(jù)庫頻繁動(dòng)態(tài)更新的情況。
　　 當(dāng)數(shù)據(jù)庫出現(xiàn)增刪改時(shí)，不得不重新建立索引。為了適應(yīng)動(dòng)態(tài)的圖數(shù)據(jù)庫，根據(jù)圖譜理論，將圖的拓?fù)湫畔⒂成涞綌?shù)據(jù)空間中；并根據(jù)映射的數(shù)值空間，建立相應(yīng)的索引結(jié)構(gòu)。這種方法不但加快了過濾的時(shí)間，且可以動(dòng)態(tài)的維護(hù)索

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

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