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

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

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

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