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

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

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

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