大圖上子圖匹配算法研究.pdf

1、子圖匹配是圖算法研究的一個主要問題。子圖匹配問題的定義是給出查詢圖，從大圖數(shù)據(jù)庫中找到與查詢圖結(jié)構(gòu)相同且節(jié)點標簽相同的所有子圖。但在實際的應(yīng)用中，用戶往往只關(guān)心一些匹配得分較高的結(jié)果。因此便引入了Top-K子圖匹配問題。Top-K子圖匹配問題與子圖匹配問題相似，不同之處在于Top-K子圖匹配問題會對結(jié)果進行排序，最終返回k個得分較高的子圖。因此對于返回全部子圖匹配的問題，Top-K子圖匹配問題顯得更有針對性。本文針對圖數(shù)據(jù)處理中的Top

2、-K子圖匹配查詢進行研究，具體研究內(nèi)容如下。
　　首先，子圖匹配方法主要采用過濾-驗證模式進行查詢，則過濾效果和驗證效果將是影響算法效率的兩個主要因素。通過對現(xiàn)有的子圖匹配問題處理方法的分析，發(fā)現(xiàn)在過濾階段現(xiàn)有方法主要存在以下問題：(1)等價節(jié)點重復枚舉問題；(2)基于路徑結(jié)構(gòu)過濾開銷過大的問題；(3)匹配順序不當問題。在驗證階段則存在大量冗余驗證問題。
　　其次，在過濾階段，提出PFilter算法，針對等價節(jié)點重復枚舉問題

3、，提出圖壓縮策略，將等價節(jié)點壓縮從而減少枚舉。針對基于路徑過濾開銷過大的問題，提出只考察直接鄰居作為過濾方法，從而減少開銷。針對匹配順序不當問題，提出對查詢圖中候選節(jié)點最少的節(jié)點作為匹配起始節(jié)點，向圖的兩端進行深度優(yōu)先探查。
　　再次，在驗證階段，提出PGetScore算法，針對造成大量冗余驗證的問題，提出利用RWM(ranking while matching)思想，對算法進行提前終止，從而減少冗余驗證。
　　最后，通過實