利用頻繁子圖支持子圖近似匹配的索引技術(shù)研究.pdf

1、作為數(shù)學(xué)的一個新的分支，圖論起源于著名的哥尼斯堡七橋問題，它以圖作為研究對象。近年來受計算機(jī)科學(xué)技術(shù)飛速發(fā)展地刺激，圖論的發(fā)展極其迅速。其應(yīng)用范圍不斷拓廣，出現(xiàn)了越來越多的以圖形建模的數(shù)據(jù)，例如化合物分子，蛋白質(zhì)交互網(wǎng)絡(luò)等。隨著這些數(shù)據(jù)規(guī)模不斷地增大，如何有效地管理和挖掘海量的圖數(shù)據(jù)成為圖數(shù)據(jù)庫研究的核心問題。
　　近年來，圖數(shù)據(jù)庫中的近似查詢逐漸引起了越來越多的關(guān)注，但由于圖數(shù)據(jù)自身結(jié)構(gòu)的復(fù)雜性，如何從海量的圖數(shù)據(jù)中迅速找到近似

2、滿足給定查詢要求的答案成為一個挑戰(zhàn)。針對這個問題，本文通過分析圖的頻繁結(jié)構(gòu)和拓?fù)潢P(guān)系，定義了一種新的圖相似性度量的標(biāo)準(zhǔn)，并在此基礎(chǔ)上提出了一種有效的針對近似圖包含搜索的索引構(gòu)造方法，極大地提高了查詢的效率。本文的研究成果主要有:
　　(1)提出了一種新的衡量圖相似性的標(biāo)準(zhǔn)。本文從圖編輯距離的定義入手，進(jìn)而研究圖之間的拓?fù)潢P(guān)系，并給出了圖之間近似程度的形式化表達(dá)。該表達(dá)為本文提出的近似查詢算法提供了理論基礎(chǔ)。
　　(2)提出一

3、種新的基于頻繁子圖的索引結(jié)構(gòu)—倒排頻繁子圖索引，進(jìn)一步將兩個圖之間的編輯距離計算拓展到整個數(shù)據(jù)庫，以避免時間效率很差的順序查找。
　　(3)發(fā)現(xiàn)了利用頻繁子圖性質(zhì)可以加速公共頻繁子圖的匹配過程。提出了分層倒排頻繁子圖索引(LIF-Index)的方法，使用分層關(guān)聯(lián)結(jié)構(gòu)組織頻繁子圖項的索引，形成基于頻繁頂點的子圖查詢方法。實驗表明，該方法有效地提高了子圖的查詢效率。
　　(4)將過濾原理進(jìn)一步應(yīng)用到分層倒排頻繁子圖索引(LIF-