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

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

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