基于Spark的圖數(shù)據(jù)查詢算法研究.pdf

1、圖是一種重要的數(shù)據(jù)結(jié)構(gòu)，有著強(qiáng)大的信息表達(dá)能力，可以描述現(xiàn)實(shí)中諸多網(wǎng)絡(luò)類型的問題。隨著互聯(lián)網(wǎng)中數(shù)據(jù)規(guī)模的增長，其形成的圖結(jié)構(gòu)越來越復(fù)雜，如何在大規(guī)模數(shù)據(jù)圖中有效地進(jìn)行圖數(shù)據(jù)查詢是當(dāng)前關(guān)注的問題。
　　子圖同構(gòu)算法是圖數(shù)據(jù)查詢的核心。子圖同構(gòu)問題被證明是一個NP完全問題，不存在多項(xiàng)式時間內(nèi)的算法，為了能夠在可接受時間內(nèi)完成大規(guī)模數(shù)據(jù)圖下的查詢，理想的解決方案是設(shè)計高效算法同時提高處理平臺的性能。提高子圖同構(gòu)查詢算法的性能需要從索引策

2、略、剪枝規(guī)則、候選集生成策略和匹配規(guī)則四個方面著手改進(jìn)，以求算法從局部到整體效率的提高。針對上述問題，論文進(jìn)行了以下工作。
　　首先，論文研究并設(shè)計了一種基于頂點(diǎn)和鄰域信息的索引VNIndex。該索引的主要原理是將數(shù)據(jù)圖中所有頂點(diǎn)與其周圍鄰居頂點(diǎn)建立單獨(dú)的聯(lián)系，探測與鄰居頂點(diǎn)形成的點(diǎn)邊信息，將這些信息整理構(gòu)建形成以自身頂點(diǎn)為核心的索引數(shù)據(jù)。該索引結(jié)構(gòu)能夠壓縮圖數(shù)據(jù)，實(shí)現(xiàn)在最小索引規(guī)模下有效地檢索信息。
　　其次，論文設(shè)計了一

3、種基于VNIndex索引結(jié)構(gòu)的精確子圖同構(gòu)查詢算法VNQuery。剪枝方面，算法設(shè)計并應(yīng)用了一種先期剪枝和匹配中剪枝相結(jié)合的剪枝策略，細(xì)化了剪枝規(guī)則，提高了剪枝效果;候選集生成方面，算法中設(shè)計并實(shí)現(xiàn)了一種改進(jìn)的候選集生成策略和基于鄰域擴(kuò)展的頂點(diǎn)查找順序，減少了候選集生成規(guī)模，加快了查找速度;頂點(diǎn)匹配方面，算法設(shè)計了一種改進(jìn)的頂點(diǎn)匹配規(guī)則，使用四種合計七條匹配規(guī)則進(jìn)行匹配頂點(diǎn)的確認(rèn)，完成匹配的同時進(jìn)行細(xì)粒度的剪枝。
　　論文利用Gr