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

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

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

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