圖數(shù)據(jù)精確查詢與近似查詢的研究.pdf

1、隨著現(xiàn)代信息技術(shù)的高速發(fā)展,數(shù)據(jù)的結(jié)構(gòu)形式變得越來(lái)越復(fù)雜。圖作為一種一般數(shù)據(jù)結(jié)構(gòu),能夠?qū)?fù)雜結(jié)構(gòu)的數(shù)據(jù)以及數(shù)據(jù)和數(shù)據(jù)之間存在的相互關(guān)系進(jìn)行建模,這使得圖數(shù)據(jù)管理的應(yīng)用領(lǐng)域越來(lái)越廣泛,比如在醫(yī)藥信息學(xué)、生物信息學(xué)、社會(huì)網(wǎng)絡(luò)、地理信息系統(tǒng)等。
　　圖查詢作為圖數(shù)據(jù)管理的一個(gè)重要研究方向,具有廣泛的研究意義,能夠幫助人們從大量的復(fù)雜數(shù)據(jù)中快速檢索到有價(jià)值的信息。作為一門(mén)新興的學(xué)科,越來(lái)越多的研究人員正在關(guān)注數(shù)據(jù)查詢領(lǐng)域。
　　目前

2、,圖數(shù)據(jù)查詢基本上都采用“過(guò)濾-驗(yàn)證”機(jī)制,先對(duì)需要查詢的數(shù)據(jù)進(jìn)行過(guò)濾,得到候選集,再對(duì)候選集進(jìn)行精確驗(yàn)證。過(guò)濾的目的是為了盡量減少驗(yàn)證的次數(shù),而圖的驗(yàn)證主要是進(jìn)行圖的同構(gòu)測(cè)試。眾所周知,圖的同構(gòu)測(cè)試已被業(yè)界證明為是一個(gè)NP難題。如何更為有效的獲取候選集,降低計(jì)算復(fù)雜度,提高查詢的效率,是一個(gè)具有廣泛實(shí)際意義的研究課題。
　　因此,為了提高查詢的效率,研究人員采用在圖數(shù)據(jù)庫(kù)管理系統(tǒng)中對(duì)圖數(shù)據(jù)庫(kù)建立索引結(jié)構(gòu)。用離線的建立索引的時(shí)間和

3、空間消耗,來(lái)減少在線的查詢執(zhí)行的時(shí)間和空間消耗。本文就圖查詢過(guò)濾階段如何有效構(gòu)建索引做了以下工作:
　　首先,本文介紹了圖查詢的基本概念,圖查詢的類(lèi)型,圖查詢技術(shù)的分類(lèi)以及圖數(shù)據(jù)研究中存在的主要問(wèn)題,并且詳細(xì)介紹了幾種經(jīng)典的圖查詢算法,分析歸納了這些算法的優(yōu)缺點(diǎn),為后面的研究工作奠定了一定的理論基礎(chǔ)。
　　其次,針對(duì)圖的精確匹配查詢,本文利用頻繁子圖建立索引,提出了一種新的索引算法,解決了GIndex算法中存在的“沖突”問(wèn)題

4、。算法首先由頻繁子圖得到特征集,將特征集組織到DFS樹(shù)中,并對(duì)其進(jìn)行DFS編碼,使特征圖序列化,最后利用雙哈希函數(shù)將其實(shí)現(xiàn)存儲(chǔ),建立索引。整個(gè)算法解決了編碼過(guò)程中的“沖突”問(wèn)題,使得“過(guò)濾”階段效率更高。
　　再次,針對(duì)圖近似查詢問(wèn)題,本文提出一種新的查詢方法。算法采用在圖的拓?fù)浣Y(jié)構(gòu)類(lèi)型上進(jìn)行近似查詢,對(duì)圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行解構(gòu),得到不同尺寸的項(xiàng)集并組織在DAG圖中,再由查詢圖的最小生成樹(shù)找到最大公共子結(jié)構(gòu),對(duì)其進(jìn)行擴(kuò)展,得到滿足近似