面向Web規(guī)模圖數(shù)據(jù)的子圖匹配算法的研究與實現(xiàn).pdf

1、圖作為計算機學科中一種抽象的數(shù)據(jù)結(jié)構，具有很強的表達能力?，F(xiàn)實生活中的很多錯綜復雜的關系都用圖作為數(shù)據(jù)模型來描述，例如蛋白質(zhì)交互網(wǎng)絡，化學分子結(jié)構，社交網(wǎng)絡等。但是這種超強的表達能力也導致了圖數(shù)據(jù)上的各種算法難度大大增加。圖上的很多問題是NP-完全問題。近些年隨著信息技術以及計算機網(wǎng)絡的飛速發(fā)展，尤其是互聯(lián)網(wǎng)的日益普及，各個領域的數(shù)據(jù)量猛增，而從導致了圖的規(guī)模也迅速擴充。如何在這樣龐大規(guī)模的圖中找到所需要的信息，一方面是迫切需要解決的實

2、際問題，一方面解決這個問題又存在嚴峻的挑戰(zhàn)。所以基于Web規(guī)模圖數(shù)據(jù)查詢成為了研究熱點。
　　子圖匹配算法是圖數(shù)據(jù)查詢的一項基本操作，具有重要的研究價值。本文中子圖匹配是指在單一Web規(guī)模圖數(shù)據(jù)庫中，通過子圖同構找到所有匹配集合。它面臨的主要問題就是子圖同構問題。子圖同構問題已經(jīng)證明是NP完全問題，這就意味著查詢效率低。為了提高查詢效率，本文主要是從建立索引結(jié)構和分布式并行處理兩個方面來考慮，并進行深入研究，分別提出了基于索引的子

3、圖匹配方法和基于云環(huán)境的子圖匹配方法。
　　在基于索引的子圖匹配算法中，主要針對以往算法一次匹配一點的弊端進行改進，提出一次匹配一條路徑的方法，從而建立了基于最短路徑索引的子圖匹配算法。主要是通過為Web規(guī)模圖上的每個頂點鄰居信息建立壓縮結(jié)構來完成，這種結(jié)構是由頂點鄰居組成的最短路徑所構成。由于這種索引可以一次匹配一條路徑，所以對Web規(guī)模圖有很好的擴展性。
　　在基于云計算環(huán)境子圖匹配算法中，采用了基于內(nèi)存云的分布式圖數(shù)據(jù)