圖數(shù)據(jù)查詢技術(shù)的研究.pdf_第1頁(yè)
已閱讀1頁(yè),還剩139頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論