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

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

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

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