圖結構數(shù)據(jù)搜索的研究.pdf

1、隨著信息社會的信息迅速增長,人們對數(shù)據(jù)的處理有了更高的要求。由于許多數(shù)據(jù)及其關系可以比較自然地表示成圖,因而對圖數(shù)據(jù)結構的研究逐漸引起人們的關注。圖結構數(shù)據(jù)在分子生物學、化學化合物分析、基因工程、社會關系學等領域都具有重要應用價值。搜索問題是圖結構數(shù)據(jù)中最為重要的一個研究課題;搜索效率決定了圖結構數(shù)據(jù)的應用效果。
　　本文圍繞圖結構數(shù)據(jù)搜索問題展開研究。首先,從多重索引出發(fā)研究圖結構數(shù)據(jù)搜索問題;然后,在頻繁子圖挖掘算法中,提出了

2、一種決策樹來裁減子圖同構次數(shù);最后,針對搜索中的相似性搜索問題,研究相似性測量方法。取得成果如下:
　　(1)提出一種根據(jù)頻繁支持度進行迭代的圖結構數(shù)據(jù)搜索算法。這種算法思想基于如下事實:索引數(shù)量和索引能力都會受到頻繁支持度的影響。具體過程是利用FSG頻繁子圖生成算法在不同支持度下多次迭代,在每次迭代中裁剪圖數(shù)據(jù)庫的搜索空間和頻繁子圖的數(shù)量。實驗表明,該算法達到了預定的提高搜索效率的目的。
　　(2)提出了一種裁剪子圖同構次

3、數(shù)的頻繁子圖決策樹。首先基于向下閉包性質對頻繁子圖構建頻繁子圖決策樹,然后利用頻繁子圖決策樹解決頻繁子圖生成算法中多次搜索數(shù)據(jù)庫或候選集時進行子圖同構次數(shù)多的問題,從而通過裁減頻繁子圖同構次數(shù),提高了頻繁子圖挖掘算法的效率。另外,本文給出了構建頻繁子圖決策樹的寬度優(yōu)先子圖同構法的算法實現(xiàn)。通過裁剪子圖同構的數(shù)量提高了挖掘算法的效率,給出了一條提高頻繁子圖挖掘算法的新道路。
　　(3)提出了一種結合拓撲子圖與編輯距離的測量方法。這種