基于分類的圖索引方法研究.pdf

1、隨著圖結(jié)構(gòu)在復(fù)雜數(shù)據(jù)建模方面的廣泛應(yīng)用，圖數(shù)據(jù)庫技術(shù)得到了快速發(fā)展。如何從圖數(shù)據(jù)庫中快速檢索數(shù)據(jù)已經(jīng)成為一個研究熱點。在圖查詢中，子圖匹配查詢和相似性查詢是兩種重要的查詢方式。子圖匹配查詢是指返回數(shù)據(jù)庫中包含查詢圖的圖集合，而相似性查詢是返回數(shù)據(jù)庫中與查詢圖相似的圖集合。處理子圖匹配查詢和相似性查詢時，分別需要進行子圖同構(gòu)驗證和圖相似度計算，但子圖同構(gòu)驗證和圖相似度計算已經(jīng)被證明是NP難題。為了快速有效地返回圖查詢的結(jié)果，目前主要采用“

2、分類過濾+驗證”兩階段處理機制。在這種機制中，首先預(yù)定義分類過濾規(guī)則，將圖數(shù)據(jù)庫分類，然后提取查詢圖特征，找到結(jié)果可能出現(xiàn)的類別，從而生成規(guī)模較小的候選集，最后對候選集進行子圖同構(gòu)驗證或者圖相似度計算得到最終的結(jié)果集。其中，人們可以根據(jù)分類過濾規(guī)則構(gòu)造合適的圖索引來提高查詢效率。
　　現(xiàn)有的用于處理子圖匹配查詢的圖索引方法中，一般都是在查詢前離線建立圖索引，而忽視了查詢圖序列在時間上的相關(guān)性，容易出現(xiàn)冗余查詢;已有的相似性查詢的圖

3、索引方法主要集中在減少相似度的計算時間，而并沒有提出一種縮小候選集規(guī)模的方法，仍需掃描整個數(shù)據(jù)庫才能得到結(jié)果集。
　　針對以上子圖匹配查詢問題，本文提出了一種雙索引的方法。其主要思想是:首先采用傳統(tǒng)方法，基于圖數(shù)據(jù)庫離線建立圖索引DIndex(Database Index);然后在查詢過程中，在線實時建立圖索引HIndex(History Index)。HIndex中存放的是根據(jù)查詢熱度得到的一組頻繁查詢結(jié)構(gòu)。這樣當(dāng)某些圖被重復(fù)查

4、詢時，可以首先搜索HIndex，如果搜索成功，即可直接得到結(jié)果集，從而避免子圖同構(gòu)驗證;如果搜索失敗，則可按照傳統(tǒng)方法搜索基于圖數(shù)據(jù)庫建立的索引DIndex，得到候選集。
　　為了縮小相似性查詢問題中候選圖的規(guī)模，本文提出了一種多層過濾方法，并針對于不同的過濾層，分別提出了相適應(yīng)的索引結(jié)構(gòu)。首先將查詢圖的規(guī)模信息和頂點標(biāo)簽信息與圖數(shù)據(jù)庫中的圖進行比較，將高偏差的圖剔除;然后利用本文提出的基于子圖向量異或乘積的計算方法得到一個有序集

5、合，使得可能滿足查詢要求的圖聚集在該集合的前半部分;之后本文采用類似二分查找的方式，通過計算映射距離，動態(tài)調(diào)整得到一個合適的下標(biāo)值，使得可能滿足要求的圖都出現(xiàn)在該下標(biāo)的左側(cè)，這樣就可以將該下標(biāo)左側(cè)的圖直接加入到候選集;為了提高結(jié)果集的查全率，有序集合中出現(xiàn)在下標(biāo)右側(cè)的圖也有一部分被選入候選集。最后，通過計算候選集中的圖編輯距離，返回滿足查詢要求的圖集合。
　　最后，本文通過實驗驗證了雙索引方法和多層過濾方法在子圖匹配查詢和圖相似性

6、查詢中的有效性。在子圖匹配查詢的實驗中，本文采用不同密度的查詢序列進行查詢，得到雙索引方法和傳統(tǒng)單索引方法以及無索引方法在不同情況下的平均子圖同構(gòu)次數(shù)。分析實驗結(jié)果發(fā)現(xiàn)，隨著查詢密度的增大，雙索引方法中子圖同構(gòu)驗證的次數(shù)與已有的兩種經(jīng)典方法相比明顯減少，從而提高了查詢效率。在相似性查詢實驗中，本文分別從索引建立時間，索引大小以及索引性能以及查全率四個方面將多層過濾方法與已有的Closure-Tree方法進行對比。實驗結(jié)果表明，多層過濾方