大圖上高效的子圖匹配算法設(shè)計(jì)與實(shí)現(xiàn).pdf

1、在大數(shù)據(jù)時(shí)代，海量多源異構(gòu)數(shù)據(jù)之間存在著復(fù)雜、緊密的關(guān)系，用圖結(jié)構(gòu)作為描述數(shù)據(jù)間復(fù)雜的關(guān)系被廣泛應(yīng)用于各個(gè)領(lǐng)域。但是，隨著這些領(lǐng)域的蓬勃發(fā)展，以圖為結(jié)構(gòu)的數(shù)據(jù)量也呈指數(shù)型爆炸式增長。而子圖匹配作為圖數(shù)據(jù)處理中的一項(xiàng)基本操作，備受學(xué)術(shù)界和工業(yè)界所關(guān)注。如何根據(jù)用戶自定義的查詢結(jié)構(gòu)，在大規(guī)模數(shù)據(jù)圖上高效地返回滿足用戶要求的匹配成為目前首要研究問題。然而，之前的工作，多數(shù)都是在無權(quán)圖上的查詢，并沒有考慮用戶的個(gè)性化需求，并且目前算法在大規(guī)模數(shù)

2、據(jù)圖上的執(zhí)行時(shí)間和效果并不是很理想。本文對目前子圖匹配問題中的存在的不足進(jìn)行了改進(jìn)和創(chuàng)新，主要研究成果及貢獻(xiàn)如下:
　　對于大規(guī)模數(shù)據(jù)圖上的個(gè)性化子圖匹配算法進(jìn)行研究，首先通過已有的社團(tuán)檢測GN算法將數(shù)據(jù)圖劃分成若干個(gè)子區(qū)域，2個(gè)線下索引結(jié)構(gòu):GP-Tree索引和排序邊集索引;然后基于索引結(jié)構(gòu)，通過增加優(yōu)化策略來加速子圖匹配;最后，通過實(shí)驗(yàn)證明了該算法的有效性和擴(kuò)展性。
　　對于大規(guī)模數(shù)據(jù)圖上的并行子圖匹配算法進(jìn)行研究，利用