巨型圖結構數據的在線上分析模型及算法研究

《巨型圖結構數據的在線上分析模型及算法研究》是依託浙江大學，由貝毅君擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：巨型圖結構數據的在線上分析模型及算法研究
• 依託單位：浙江大學
• 項目負責人：貝毅君
• 項目類別：青年科學基金項目

項目摘要

作為對象以及對象關係的建模工具，圖結構的分析和研究一直是學術界的關注熱點。目前主要從靜態統計、頻繁模式挖掘、動態總結等技術手段研究和分析圖結構數據。隨著網際網路的發展以及社會化網路套用的大量湧現，需要從不同粒度、維度、層次對巨型圖結構進行分析和理解，但現有的方法還無法有效解決巨型圖結構的多角度分析問題。本項目提出一個面向巨型圖結構的在線上分析模型，在此模型基礎上對巨型圖存儲結構、多維子圖索引機制、多粒度物化視圖機制、面向圖聚集的查詢分析算法等一系列算法和技術進行研究，進而部分解決社會化網路領域引出的圖數據分析問題。所構建的圖分析系統將使得用戶可自由選擇其所感興趣的節點和關係屬性，執行不同維度和層次上的圖數據聚集操作，方便用戶在不同粒度、角度、層面上分析並理解圖信息。本項目根據圖數據分析和管理的新需求，嘗試為圖數據尤其是巨型圖的分析開闢一條新思路。項目的研究在理論和實踐兩方面都將具有重要意義。

結題摘要

隨著網際網路的發展以及社會化網路套用的大量湧現，需要從不同粒度、維度、層次對巨型圖結構進行分析和理解，但現有的方法還無法有效解決巨型圖結構的多角度分析問題。本項目旨在提出一個面向巨型圖結構的在線上分析模型，在此模型基礎上對巨型圖存儲結構、多維子圖索引機制、多粒度物化視圖機制、面向圖聚集的查詢分析算法等一系列算法和技術進行研究，進而部分解決社會化網路領域引出的圖數據分析問題。所構建的圖分析系統將使得用戶可自由選擇其所感興趣的節點和關係屬性，執行不同維度和層次上的圖數據聚集操作，方便用戶在不同粒度、角度、層面上分析並理解圖信息。 項目主要研究內容和取得成果如下：1.研究巨型圖結構的維度、層次、度量手段等概念，設計可多粒度分析和處理巨型圖結構的在線上分析框架；2.研究巨型圖數據模型，設計滿足巨型圖查詢和分析的高效存儲模型和數據訪問機制；3.研究支持在線上分析的圖索引算法和圖立方的物化視圖機制，設計圖立方體的多粒度物化視圖機制和索引機制，設計支持多維、多層次的物化策略及基於子圖結構的多維圖數據索引算法；4. 研究圖數據的各種聚集操作方法，設計支持圖數據多維分析如上卷、下鑽、切片、切塊等操作的聚集最佳化算法；5.研究圖多維數據集的套用，實現查詢處理和最佳化算法，研發支持圖數據聯繫分析的原型系統。