面向Web社會網路的查詢處理關鍵技術研究

《面向Web社會網路的查詢處理關鍵技術研究》是依託復旦大學，由肖仰華擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：面向Web社會網路的查詢處理關鍵技術研究
• 依託單位：復旦大學
• 項目類別：青年科學基金項目
• 項目負責人：肖仰華

項目摘要

近年來，隨著網際網路套用的不斷深化以及Web社會性特徵的不斷增強， Web社會網路，即各類Web實體及其之間的關係，日益成為了Web上的一種新穎的、重要的數據類型。與此同時，Web社會網路的查詢套用以及高質量的Web社會網路分析，都對Web社會網路上的高效查詢處理技術提出了需求。然而Web社會網路的海量規模、不確定性和動態性對於圖查詢處理技術提出了全新的挑戰。針對這些挑戰，本項目擬基於Web社會網路的結構特徵和演化規律，從查詢處理、數據組織和查詢最佳化三個方面對面向Web社會網路數據的查詢處理關鍵技術展開研究，以期提出一系列Web社會網路查詢處理關鍵理論、技術和方法。本項目對於進一步提升圖數據管理的研究水平、實現面向大圖的數據管理系統具有重要的學術意義；對於提高Web社會網路分析質量、滿足現實套用中的Web社會網路查詢需求，具有實際套用價值。

結題摘要

本課題在基金資助下獲得豐碩成果。先後在CCF A類會議SIGMOD、VLDB、ICDE、ICSE、SPLASH；國際四大綜合SCI期刊Plos One(影響因子4)發表論文。截止結題，已累計發表5篇A類會議、4篇B類會議、3篇SCI影響因子1.0以上的期刊論文。這些成果針對大規模Web社會網路的查詢處理、數據組織、查詢最佳化展開研究，在可重疊社團搜尋、帶約束的可達性查詢、最短距離查詢最佳化、分散式圖數據組織、數據壓縮方法、數據編碼方法等方面提出了新穎的模型以及高效的解決方法；並以Web社會網路的可視化與結構分析為套用示例，論證了模型與方法的有效性。 其中發表於SIGMOD2013的《Online search of overlapping communities》所提出的可重疊社團搜尋模型及相應的近似算法代表了當前國際上社團搜尋領域最前沿技術。發表於PVLDB2013的《Toward a Distance Oracle for Billion-Node Graphs》提出的最短距離查詢方案是目前國際該問題能夠處理的最大規模Web社會網路。發表於ICDE2012《Branch Code: An Efficient Labeling Scheme for Query Answering on Trees》針對以XML格式存儲的web社會網路提出了一種新穎的數據編碼方法，在支持多種關係查詢的同時，有著較低的存儲代價。 基於上述理論成果，先後發布了具有自主智慧財產權的GraphExplorer、XMLSnippet、SCuV、CGAP-Align等系統，分別套用於社會網路分析、代碼關係分析、基因組序列分析等領域。部分算法在微軟研究院的大規模圖資料庫系統Trinity中得以採用。 本課題成果突出，在國內外產生一定影響力。課題負責人肖仰華博士在SIGMOD2012做了題為《Managing and Mining Large Graphs: Systems and Implementations》會議輔導（Tutorial），並應邀在HOTDB2012、HOTDB2013做大會報告。成果獲得教育部2012年高校優秀科研成果二等獎，肖仰華博士獲得ACM上海傑出青年科學家提名獎等等榮譽。課題組成果先後7次參加國際頂級會議並作論文報告。課題組先後培養了4位博士、3名碩士。