基于V--index的子圖查詢算法的研究與實(shí)現(xiàn).pdf

1、圖是計(jì)算機(jī)科學(xué)技術(shù)中一種重要的數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷發(fā)展，出現(xiàn)了越來越多的以圖為邏輯表達(dá)的數(shù)據(jù)。例如社會(huì)網(wǎng)路，蛋白質(zhì)交互網(wǎng)絡(luò)，分子化學(xué)式等等。而且，這些圖數(shù)據(jù)的數(shù)量也在不斷地增加，例如社交網(wǎng)站上的注冊(cè)用戶多達(dá)幾千萬甚至是上億，從而產(chǎn)生了基于互聯(lián)網(wǎng)的大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)。如何有效地管理這些數(shù)據(jù)，已逐漸成為信息化領(lǐng)域中熱門研究問題之一。對(duì)圖的操作具體包括:
　　(1)如何建立有效地存儲(chǔ)機(jī)制和索引策略；
　　(2)如何在

2、海量圖數(shù)據(jù)庫中進(jìn)行高效的查詢。
　　在圖上進(jìn)行子圖查詢是圖數(shù)據(jù)管理的基本操作之一。子圖查詢的定義是:給定一個(gè)查詢圖Q和一個(gè)數(shù)據(jù)圖G，在數(shù)據(jù)圖G中尋找所有與查詢圖Q匹配的子圖。目前的子圖查詢算法多數(shù)采用子圖同構(gòu)算法，由于子圖同構(gòu)算法是典型的NP-完全問題，其查詢效率非常低。為了改善子圖查詢算法的效率，本文提出了一種基于頂點(diǎn)編碼的方式來創(chuàng)建數(shù)據(jù)圖的索引，在這種索引基礎(chǔ)上進(jìn)行子圖查詢操作。為了降低查詢匹配的次數(shù)，首先對(duì)索引結(jié)構(gòu)進(jìn)行剪枝，

3、然后根據(jù)查詢頂點(diǎn)信息查找頂點(diǎn)匹配對(duì)，最后在頂點(diǎn)匹配對(duì)中查找匹配子圖。由于基于頂點(diǎn)編碼的索引結(jié)構(gòu)是以整個(gè)數(shù)據(jù)圖為單位創(chuàng)建的，索引結(jié)構(gòu)不易更改而且索引表所占內(nèi)存空間比較大。為了減少索引空間的利用，本文對(duì)基于頂點(diǎn)編碼的子圖查詢進(jìn)行改進(jìn)，提出了一種基于代碼塊的子圖查詢算法，這種算法的基本思想是:將數(shù)據(jù)圖分割成無數(shù)小的分區(qū)，然后再在這些小的分區(qū)中查找子圖。由于這種算法存在匹配過界問題，所以我們對(duì)交叉邊也進(jìn)行存儲(chǔ)。并且在查詢過程中，遍歷交叉邊索引，