基于gSpan的數(shù)據(jù)篩選算法研究與應(yīng)用

0 引言

圖模型作為一種一般的數(shù)據(jù)結(jié)構(gòu)，因其能夠清晰直觀地表示復(fù)雜的結(jié)構(gòu)而被廣泛應(yīng)用于許多科學(xué)領(lǐng)域。但是隨著圖模型應(yīng)用越來越廣泛，圖結(jié)構(gòu)數(shù)據(jù)庫越來越大，如何快速有效地查詢特定圖結(jié)構(gòu)就成為了人們研究的熱點和難點。圖查詢的最基本方法是將目標圖和數(shù)據(jù)庫中的圖集進行一一匹配，直到找出日標圖為止。而圖的匹配已被證明是NP完全問題，其算法復(fù)雜度是圖規(guī)模的指數(shù)函數(shù)，造成了圖匹配的優(yōu)化算法改進難度較大。因此研究重點集中在預(yù)篩選上，最常用的篩選技術(shù)有片斷位串和指紋技術(shù)。它們首先對數(shù)據(jù)庫中的圖結(jié)構(gòu)進行編碼建立特征庫，其次對目標圖進行特征提取，然后直接對比數(shù)據(jù)庫中的結(jié)構(gòu)特征，把符合結(jié)構(gòu)特征的記錄集提取出來，最后進行匹配。這種編碼沒有特定的規(guī)則，只是按照具體情況選擇最有利的實現(xiàn)方法進行編碼，因此其應(yīng)用范圍有限，而且隨著數(shù)據(jù)庫增大，圖形結(jié)構(gòu)越來越復(fù)雜，如何選擇最有利的方法進行特征編碼將是一個非常棘手的問題。