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

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

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

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

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