一種面向模式圖變化的增量圖模式匹配算法

　　在大數(shù)據(jù)時(shí)代，數(shù)據(jù)圖的規(guī)模急劇增長，增量圖模式匹配算法能夠在數(shù)據(jù)圖或模式圖發(fā)生變化時(shí)避免重新在整個(gè)數(shù)據(jù)圖上進(jìn)行匹配、減少響應(yīng)時(shí)間，因此成為了研究的熱點(diǎn)．針對實(shí)際應(yīng)用中數(shù)據(jù)圖不變而模式圖發(fā)生變化的情況，提出了一種面向模式圖變化的增量圖模式匹配算法PGC IncGPM，在模式圖匹配的過程中記錄適當(dāng)?shù)闹虚g結(jié)果作為索引，用于后續(xù)的模式匹配．提出了增強(qiáng)的圖模式匹配算法GPMS，用于首次整個(gè)數(shù)據(jù)圖上的模式匹配．該算法一方面能夠建立后續(xù)增量匹配所需的索引，另一方面減少了整個(gè)數(shù)據(jù)圖匹配的執(zhí)行時(shí)間．設(shè)計(jì)實(shí)現(xiàn)了面向模式圖增邊和減邊的兩個(gè)核心子算法，通過子算法的組合，能夠支持在模式圖發(fā)生各種變化時(shí)進(jìn)行增量圖模式匹配．在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明：與重新在整個(gè)數(shù)據(jù)圖上進(jìn)行匹配的ReComputing算法相比，當(dāng)模式圖中變化的邊的數(shù)目不超過不變的邊的數(shù)目時(shí)，PGC_ IncGPM算法能夠有效減少圖模式匹配的執(zhí)行時(shí)間；隨著數(shù)據(jù)圖規(guī)模的增大，PGC IncGPM算法相對于ReComputing算法的執(zhí)行時(shí)間的減少程度更加明顯，對于大規(guī)模數(shù)據(jù)圖具有更好的適用性。