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

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

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

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