超大規(guī)模社交圖上的子圖匹配問題研究.pdf

1、圖是一種以頂點(diǎn)和邊為基礎(chǔ)形成的一種結(jié)構(gòu)化數(shù)據(jù)表現(xiàn)形式，相比傳統(tǒng)的數(shù)據(jù)庫表形式，具有非常靈活的表達(dá)能力。近些年來，Twitter，F(xiàn)acebook,微博，微信等社交工具的出現(xiàn)，產(chǎn)生了超大規(guī)模的社交圖數(shù)據(jù)。如何處理超大規(guī)模的圖數(shù)據(jù)成為了非常關(guān)鍵的研究問題。子圖匹配問題是圖數(shù)據(jù)處理領(lǐng)域中的一個非常基礎(chǔ)和重要的問題。圖上的搜索，模式挖掘算法都必須基于快速的子圖匹配算法。
　　子圖匹配問題是一個NP難問題，前人的研究工作中給出了一些純算法的

2、解法，這些方法難以處理十幾萬頂點(diǎn)以上規(guī)模的圖數(shù)據(jù)。也有一些工作通過建立索引的方式來處理大規(guī)模的圖數(shù)據(jù)，但是這些索引的規(guī)模都是圖規(guī)模的超線性函數(shù)，在圖規(guī)模達(dá)到上億級別的社交圖時，索引的存儲代價過大，無法實(shí)現(xiàn)。
　　分布式圖數(shù)據(jù)庫的出現(xiàn)使得存儲和操作超大規(guī)模的圖數(shù)據(jù)成為現(xiàn)實(shí)。本文的工作以微軟亞洲研究院(MSRA)研究的分布式圖數(shù)據(jù)庫Trinity為底層圖數(shù)據(jù)存儲引擎，研究了超大規(guī)模圖上的子圖匹配問題，提出了一個使用線性索引，基于快速圖