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

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

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

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

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

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

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