基于Spark的子圖匹配算法研究與實(shí)現(xiàn).pdf

1、圖作為一種由頂點(diǎn)和邊構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，能夠簡(jiǎn)潔有力的表達(dá)事物之間的聯(lián)系。隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)的規(guī)模以前所未有的速度增長(zhǎng)著，F(xiàn)acebook、Twitter、微博等社交媒體每天都產(chǎn)生大量的社交圖數(shù)據(jù)。如何處理如此大規(guī)模的圖數(shù)據(jù)成為目前研究的熱點(diǎn)。其中，子圖匹配問題又是圖數(shù)據(jù)處理領(lǐng)域中最為重要的問題，圖的搜索，模式匹配等算法都需要子圖匹配算法的支持。
　　子圖匹配的數(shù)學(xué)基礎(chǔ)是圖論中的經(jīng)典問題子圖同構(gòu)，一個(gè)著名的NP完全問題。目前，

2、雖然有一些學(xué)者給出了一些方法來(lái)實(shí)現(xiàn)子圖匹配，但是這些方法只能處理小規(guī)模的圖數(shù)據(jù)，在應(yīng)對(duì)如今大規(guī)模的數(shù)據(jù)時(shí)，其匹配效率與可擴(kuò)展性都有很大不足。另外，多數(shù)子圖匹配算法應(yīng)用于無(wú)向圖，在有向圖的應(yīng)用上存在著不適用或效率低下的問題。
　　針對(duì)以上問題。本文依托近些年來(lái)興起的大數(shù)據(jù)平臺(tái)，利用其提供強(qiáng)大的存儲(chǔ)與計(jì)算能力，研究并實(shí)現(xiàn)了以大數(shù)據(jù)處理平臺(tái)Spark作為處理引擎，應(yīng)用GraphX組件處理超大規(guī)模圖數(shù)據(jù)的子圖匹配算法。該算法以HDFS為存

3、儲(chǔ)平臺(tái)，有效解決了集群負(fù)載均衡問題;計(jì)算過程分為分布式過濾階段與分布式驗(yàn)證階段。
　　分布式過濾階段充分考慮Spark平臺(tái)特性與GraphX以頂點(diǎn)為分割的圖分割策略，提出頂點(diǎn)簽名數(shù)據(jù)結(jié)構(gòu)，通過并行比對(duì)頂點(diǎn)簽名的方式實(shí)現(xiàn)對(duì)數(shù)據(jù)圖快速高效過濾。其中，頂點(diǎn)簽名中表達(dá)了自身與鄰域信息，鄰域中又區(qū)分父鄰域與子鄰域，提升了對(duì)有向圖的過濾效果。
　　分布式驗(yàn)證階段利用Spark平臺(tái)分布式計(jì)算優(yōu)勢(shì)，提出候選子圖匹配區(qū)域概念，通過對(duì)查詢圖中心