【摘要】：圖匹配是圖數(shù)據(jù)應(yīng)用的重要技術(shù)手段。與基于子圖同構(gòu)的匹配方法相比,圖模擬放松了結(jié)構(gòu)匹配要求,有效提升了圖匹配效率。然而,對(duì)于大規(guī)模圖數(shù)據(jù)上的圖匹配而言,已有的基于模擬的圖匹配方法仍然不能滿(mǎn)足高效匹配的要求。針對(duì)這一問(wèn)題,本文在已有的圖模擬方法的基礎(chǔ)上,提出了基于Pregel編程模型的并行化的圖模擬匹配方法。本文的主要研究工作和貢獻(xiàn)有以下幾點(diǎn):首先,針對(duì)“非圈”、“有圈”兩種查詢(xún)模式,分別提出了基于Pregel編程模型的并行化圖模擬匹配方法。具體地給出了兩種查詢(xún)模式下,基于Pregel編程模型的:結(jié)點(diǎn)的消息初始化、結(jié)點(diǎn)消息響應(yīng)和處理、消息合并、消息處理方法。其次,相關(guān)集是圖匹配的重要質(zhì)量度量指標(biāo)。相關(guān)集的大小可以說(shuō)明該模式在數(shù)據(jù)圖上的覆蓋度大小。針對(duì)“非圈”、“有圈”兩種查詢(xún)模式,分別提出了基于Pregel編程模型的并行化圖匹配相關(guān)集求解方法。再次,基于Spark平臺(tái)的并行計(jì)算機(jī)組件GraphX,實(shí)現(xiàn)了基于Pregel編程模型的圖模擬匹配及相關(guān)集求解方法。最后,在真實(shí)數(shù)據(jù)集上,驗(yàn)證了本文提出基于Pregel編程模型的圖模式匹配及相關(guān)集求解方法。實(shí)驗(yàn)結(jié)果表明在獲得與已有方法相同匹配結(jié)果的情況下,本文的方法可明顯縮短匹配時(shí)間,有效地提高了算法的匹配效率。
【圖文】：

編程
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5;TP311.13

【參考文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前2條

1 馮軒;基于Pregel模型的大規(guī)模分布式子圖枚舉算法研究與實(shí)現(xiàn)[D];南京大學(xué);2017年

2 張杰;PyGel：基于DPark的分布式圖計(jì)算引擎的研究與實(shí)現(xiàn)[D];華南理工大學(xué);2013年

，

本文編號(hào)：2599134