圖結(jié)構(gòu)數(shù)據(jù)搜索的研究.pdf

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

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

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