基于偏序關(guān)系的圖查詢算法研究.pdf

1、圖模型具有強(qiáng)大的表達(dá)能力，被廣泛用于各種應(yīng)用領(lǐng)域的數(shù)據(jù)建模，如化合物的分子結(jié)構(gòu)，蛋白質(zhì)交互網(wǎng)絡(luò)以及社會網(wǎng)絡(luò)等。如何在大規(guī)模圖數(shù)據(jù)庫中進(jìn)行高效子圖包含查詢是當(dāng)前的研究難點(diǎn)之一。由于子圖同構(gòu)是一個NP完全問題，在現(xiàn)有的子圖包含查詢算法中，基于圖特征的索引技術(shù)被廣泛用來提高查詢處理性能，但是這些索引結(jié)構(gòu)的維護(hù)代價較高，不適于在線查詢。而圖數(shù)據(jù)庫具有規(guī)模大、更新頻繁的特點(diǎn)。據(jù)統(tǒng)計，平均每日約有4000個新發(fā)現(xiàn)的化合物以圖數(shù)據(jù)形式加入到SCFFi

2、nder數(shù)據(jù)庫中。因此，適用于在線查詢的子圖包含查詢算法研究非常具有實(shí)際意義。
　　針對上述問題，本文分析圖模型中的偏序關(guān)系，定義了DAG中偏序關(guān)系的概念。針對DAG，提出了基于偏序關(guān)系的圖查詢算法，首先根據(jù)圖中頂點(diǎn)間的偏序關(guān)系將圖分層拓?fù)涑梢粋€偏序序列，然后通過序列間的匹配過濾出候選結(jié)果集，最后通過子圖同構(gòu)檢測驗(yàn)證得到最終結(jié)果集。有向圖具有廣泛的應(yīng)用背景，但是有向圖中的環(huán)破壞了圖中的偏序關(guān)系。因此，本文提出環(huán)處理算法，使有向圖也

3、可拓?fù)涑善蛐蛄?，從而將本文算法擴(kuò)展到有向圖模型。實(shí)驗(yàn)結(jié)果表明，本文算法在特征提取、索引構(gòu)造以及在線查詢等方面都具有較高的性能。
　　為了進(jìn)一步提高算法性能，本文提出了兩種優(yōu)化策略：基于頂點(diǎn)局部信息的查詢優(yōu)化與基于直接偏序子序列的查詢優(yōu)化。基于頂點(diǎn)局部信息的查詢優(yōu)化算法將頂點(diǎn)局部信息附加到偏序序列中，使偏序序列包含更多的有向圖信息；基于直接偏序子序列的查詢優(yōu)化算法將查詢圖拓?fù)涑啥鄠€直接偏序子序列，增強(qiáng)了序列中的偏序關(guān)系。實(shí)驗(yàn)結(jié)果表