圖數(shù)據(jù)查詢技術(shù)的研究.pdf

1、圖是一種通用的數(shù)據(jù)結(jié)構(gòu)，能描述復(fù)雜的結(jié)構(gòu)化或半結(jié)構(gòu)化數(shù)據(jù)，如：XML、WWW、社會關(guān)系網(wǎng)絡(luò)、化合物集合、蛋白質(zhì)與基因網(wǎng)絡(luò)等等。隨著圖在各領(lǐng)域內(nèi)的成功應(yīng)用，圖數(shù)據(jù)開始迅速累積。然而，數(shù)據(jù)量的增加，不但沒有帶來信息獲取的便利，反而由于圖數(shù)據(jù)的復(fù)雜本質(zhì)，使得學(xué)習(xí)與研究工作更難展開。圖查詢是圖數(shù)據(jù)集上的一個典型應(yīng)用，用于從海量圖數(shù)據(jù)中獲取用戶需要的知識。與傳統(tǒng)查詢技術(shù)相比，圖查詢具有自己的特點(diǎn)與難點(diǎn)，如：數(shù)據(jù)結(jié)構(gòu)復(fù)雜，操控困難；子圖同構(gòu)已被證明

2、是NP完全問題，是圖查詢領(lǐng)域中不可避免的基本操作之一；圖數(shù)據(jù)種類繁雜，等等。正是這些難點(diǎn)，導(dǎo)致圖查詢技術(shù)的研究充滿了機(jī)遇與挑戰(zhàn)。
　　本文通過對圖數(shù)據(jù)查詢技術(shù)的研究，歸納總結(jié)了現(xiàn)有研究成果的思想和優(yōu)缺點(diǎn)，重點(diǎn)研究了頻繁子圖查詢、超圖查詢、包含查詢、相交子圖查詢等技術(shù)專題，主要的研究成果與創(chuàng)新如下：
　　第一、現(xiàn)有效率較高的頻繁子圖模式查詢算法，在生成頻繁子圖的過程中，對邊的擴(kuò)展通常采用深度優(yōu)先的方法。而且，對頻繁子圖的每次擴(kuò)

3、展，均需要通過子圖同構(gòu)計(jì)算驗(yàn)證其正確性。然而，深度優(yōu)先的擴(kuò)展方式雖然能有效避免查詢算法重復(fù)生成中間結(jié)果，卻帶來了更高的時(shí)間復(fù)雜性。本文提出了一種高效的頻繁子圖查詢算法，通過先生成頻繁子樹，進(jìn)而通過這些頻繁子樹進(jìn)一步生成頻繁子圖。在生成頻繁子樹的過程中，采用深度優(yōu)先的遍歷方式避免中間結(jié)果的重復(fù)計(jì)算，并利用子樹同構(gòu)可在多項(xiàng)式時(shí)間內(nèi)完成的特點(diǎn)提高該部分算法的效率。另一方面，在由子樹向子圖擴(kuò)展的過程中，通過廣度優(yōu)先的方式進(jìn)行擴(kuò)展，不但能有效避免

4、中間結(jié)果的重復(fù)生成，而且進(jìn)一步提高了算法的效率。理論分析與實(shí)驗(yàn)結(jié)果顯示，采用這種查詢方法，使查詢效率提高了O(√n· log n)倍，并在提高效率的同時(shí)，得到正確的結(jié)果集。
　　第二、超圖查詢算法采用過濾與驗(yàn)證模式，即：通過對圖集的過濾，得到更小、更精確的候選集，從而降低查詢過程中子圖同構(gòu)次數(shù)，進(jìn)而提高算法的效率。超圖查詢的過濾規(guī)則為包含邏輯，即如果甲圖包含乙圖，則甲圖必然包含乙圖的所有子圖。查詢算法的索引通常建立于圖集中的頻繁模

5、式，包括頻繁子圖、頻繁子樹或頻繁路徑等。然而，在給定查詢圖之后，無論何種索引，均需要得到查詢圖包含的索引模式，并通過索引模式支持集的交集得到候選集。在得到查詢圖包含的索引模式過程中，需要進(jìn)行查詢圖子圖枚舉，并與索引模式之間進(jìn)行子圖同構(gòu)，得到查詢圖包含的索引模式。本文提出查詢算法VFM，通過圖集中關(guān)鍵節(jié)點(diǎn)與頻繁模式之間的映射，將得到被查詢圖包含的索引模式的過程由指數(shù)形式降低為多項(xiàng)式形式，從而顯著提高了算法效率。實(shí)驗(yàn)結(jié)果表明，采用該算法進(jìn)行

6、查詢，其效率遠(yuǎn)高于當(dāng)前已經(jīng)提出的算法。
　　第三、圖查詢問題包含的另一類查詢問題，稱為包含查詢。包含查詢與超圖查詢的本質(zhì)區(qū)別在于，它采用的過濾手段為排除邏輯，即：給定查詢圖，如果圖集中的圖數(shù)據(jù)包含的某個模式不是查詢圖的子圖，則該圖也必定不是查詢圖的超圖。利用排除邏輯建立的索引，在查詢之初，同樣要通過枚舉或與索引模式之間逐個的子圖同構(gòu)計(jì)算得到不被查詢圖包含的索引模式，這是需要盡力避免的計(jì)算開銷。本文針對圖包含查詢中存在的問題，提出利

7、用頻繁子圖查詢過程中形成的深度優(yōu)先樹組織索引，能增量地進(jìn)行查詢圖與索引模式之間的子圖同構(gòu)計(jì)算。而且，在索引模式的選擇中，提出采用頻繁模式集中一類特殊的子集——頻繁閉模式來建立索引，這種方式不但能極大化地減小候選集的尺寸，同時(shí)也避免了過多子圖同構(gòu)計(jì)算所帶來的負(fù)面影響，從而提高了算法的效率。
　　第四、圖集的查詢問題，并不能完全通過頻繁子圖查詢、超圖查詢與包含查詢解決。相交子圖查詢問題，能在某些條件下轉(zhuǎn)化為超圖查詢或包含查詢。然而，超