基于頻繁子圖的圖查詢技術研究.pdf

1、隨著計算機科學與技術的發(fā)展，圖數(shù)據(jù)結構在各個領域內得到廣泛應用。圖數(shù)據(jù)管理和查詢已經(jīng)成為一種研究熱點。其中，圖查詢的基本方式分為子圖匹配查詢和圖相似性查詢。子圖匹配查詢返回圖數(shù)據(jù)庫中包含查詢圖的數(shù)據(jù)圖，圖形似性查詢返回在一定的距離范圍內與查詢圖相似的數(shù)據(jù)圖。在這兩種查詢中，分別需要圖同構驗證或相似度的計算，這兩種計算都已被證明是NP困難的，因此提升查詢的性能也只能是最大化過濾掉非結果集。目前，對于這兩種查詢的優(yōu)化，主要是基于過濾驗證機制

2、，即在查詢時通過查詢圖的特征過濾掉不符的數(shù)據(jù)圖，得到規(guī)模較小的候選集，然后對候選集進行同構驗證或者相似度的計算。其中，一般選用圖集中的頻繁子圖作為特征進行過濾，因為其保留了全局的結構信息，過濾性更強。
　　在子圖匹配查詢問題中，現(xiàn)有的方式一般是通過圖集中的特征建立索引，在查詢時對查詢圖進行邊擴展的方式得到相應的候選集。此方式在進行查詢時的時間復雜度較高，并且沒有充分利用查詢圖包含的特征進行索引的過濾，為此，本文提出了一種利用節(jié)點鄰

3、接特征進行過濾的索引結構Vindex。針對特定的領域，考慮圖集特征之間的位置關系，結合用戶的查詢記錄，提取其中較為有價值的特征位置關系，建立了基于嵌入特征關系的索引結構，用于減小候選集的大小。并提出利用特征之間的包含關系以及特征與數(shù)據(jù)圖之間的關系，在一定程度上對索引項和候選集進行縮減。
　　在圖相似性查詢問題中，現(xiàn)有的方法大多致力于減小編輯距離的計算時間，而對于縮小候選集規(guī)模沒有提出合適的索引結構和查詢過濾方法。本文結合編輯距離的

4、概念和查詢圖的結構特征，對圖集之中的數(shù)據(jù)圖進行過濾，將相差度較大的圖剔除。然后利用子圖向量異或乘的方式對圖進行聚集，將于查詢圖較為相似的圖聚集在候選集中的前一部分，然后利用分支映射距離結合動態(tài)調整的方式得到一個較為精確的候選集。在驗證階段，利用圖之間的編輯距離關系，建立了基于編輯距離的索引GDindex，在驗證時首先與在索引之中的圖進行計算，然后利用查詢圖和索引圖的編輯距離關系，對候選集中的其他數(shù)據(jù)圖進行處理，通過此種方式的處理可以減小