精確子圖數(shù)據(jù)庫(kù)查詢技術(shù)研究.pdf

1、圖是一種通用的數(shù)據(jù)結(jié)構(gòu)，相比路徑和樹結(jié)構(gòu)來(lái)說(shuō)，圖能表達(dá)更多復(fù)雜的結(jié)構(gòu)信息，如：分子結(jié)構(gòu)、社交網(wǎng)絡(luò)關(guān)系、圖像。近年來(lái)，隨著圖數(shù)據(jù)在各個(gè)應(yīng)用領(lǐng)域內(nèi)被廣泛使用，其數(shù)據(jù)量成指數(shù)級(jí)迅速積累，導(dǎo)致對(duì)這些海量數(shù)據(jù)的管理成為一項(xiàng)重要的研究工作。圖數(shù)據(jù)管理中重要的分支之一是子圖查詢技術(shù)研究。圖查詢技術(shù)具有自己的特點(diǎn)與難點(diǎn)：1、數(shù)據(jù)結(jié)構(gòu)相對(duì)其他較復(fù)雜，操縱困難。2、子圖同構(gòu)問(wèn)題在精確子圖查詢過(guò)程中是不可避免的，而且已被證明是NP難問(wèn)題。3、圖數(shù)據(jù)種類繁雜。

2、為了解決這一系列的問(wèn)題，使得圖查詢技術(shù)的研究充滿了挑戰(zhàn)與機(jī)遇。
　　本文針對(duì)圖數(shù)據(jù)庫(kù)中的精確子圖查詢技術(shù)，主要完成了以下工作：
　?。?）根據(jù)現(xiàn)有頻繁子圖挖掘算法，選取高效的頻繁子圖挖掘算法作為本論文的離線挖掘算法。通過(guò)對(duì)AGM、FSG、gSpan算法的對(duì)比，得出基于深度挖掘的gSpan算法的通用性與高效性，相比基于寬度優(yōu)先挖掘的算法來(lái)說(shuō)：1、使用DFS碼對(duì)圖進(jìn)行編碼，避免了匹配過(guò)程中的子圖同構(gòu)問(wèn)題。2、避免了Apriori

3、逐層擴(kuò)展產(chǎn)生的大量中間結(jié)果帶來(lái)的計(jì)算開銷。
　?。?）結(jié)合頻繁模式特征挖掘算法，提出一種新的基于頻繁子圖中鄰接邊哈希索引構(gòu)建方法AG-Index：利用過(guò)濾-驗(yàn)證模型，對(duì)頻繁圖部分構(gòu)建索引存入緩存內(nèi)，非頻繁部分放在磁盤，得到候選項(xiàng)后用現(xiàn)有效率較高的子圖同構(gòu)算法進(jìn)行驗(yàn)證。實(shí)驗(yàn)證明，AG-Index比經(jīng)典高效的gIndex和FG-Index算法過(guò)濾能力更強(qiáng)，內(nèi)存占有率更小，并在AG-Index的基礎(chǔ)上對(duì)其進(jìn)行了更進(jìn)一步的優(yōu)化，實(shí)驗(yàn)證明，