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

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

【參考文獻(xiàn)】

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

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

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

，

本文編號：2599134