《基於系統層次結構的大圖並行處理框架研究》是依託北京郵電大學，由張熙擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於系統層次結構的大圖並行處理框架研究
- 項目類別：青年科學基金項目
- 項目負責人：張熙
- 依託單位：北京郵電大學
項目摘要,結題摘要,
項目摘要
隨著社交網路的興起，基於大規模圖結構上的計算、分析與挖掘，成為具有重要價值的研究熱點。數據的持續增加和關聯關係的日益複雜，對並行系統結構設計和圖劃分算法的設計都提出了挑戰。本項目擬針對大規模圖並行處理中高性能、高效率和易編程的需求，通過將大圖劃分算法與系統層次化結構有機結合，提出一種新穎的大圖處理框架。該框架利用分散式系統中各層級的結構特性，建立劃分代價分析模型，設計適應各自層級需求的高效劃分方法。在此基礎上，建立統一的層次化大圖劃分框架。為了進一步提升效率，通過分析大圖數據存儲與訪問的模式，最佳化數據分布、數據複製、節點通信、I/O訪問和任務調度等機制。針對自然圖及動態圖等多種類型圖結構，提出自適應、自最佳化的處理機制。最後，構建開源框架和原型系統，並在社交網路及電信網路等套用領域中進行評估驗證。
結題摘要
隨著社交網路的興起，基於大規模圖結構上的計算、分析與挖掘，成為具有重要理論意義和套用價值的研究熱點。本項目面向大規模圖結構數據，研究如何高效處理，檢索、分析與套用。研究主要分為四個方面：（1）基於並行體系結構的大圖劃分與子圖檢索研究，包括在並行節點上的大圖劃分方法，子圖增強技術、查詢圖分解算法、子圖通信算法、頂點索引構建方法以及任務劃分和同步機制等。基於該研究，第一次實現了在以頂點為中心的圖結算模式下的子圖檢索和子圖同構算法，八節點集群上可以將子圖同構處理規模擴展到幾十萬甚至百萬級；（2）基於社交網路拓撲結構的信息傳播算法，考慮訊息間的相互作用和網路拓撲結構，基於進化博弈論和貝葉斯模型，分別提出信息傳播預測算法，為促進或抑制信息傳播提供了依據；（3）基於頂點影響力的社團發現算法，我們分析了高度數節點在大規模網路社團結構中的特別作用，基於此提出了基於頂點可變影響力的社團劃分算法。該算法可以根據實際套用場景和需求，調整劃分的方案；（4）並行體系結構的存儲性能最佳化。本項目還對並行系統地城架構開展研究，力圖提升存儲系統的性能和效率。針對多任務並行存儲空間分配的問題，提出了一種面向偽LRU算法的cache容量劃分機制。針對新型相變記憶體和固態硬碟寫延遲高的問題，提出了非對稱的讀寫替換算法。所提算法都具有良好的性能和較低的存儲和實現代價。本項目執行過程中已發表8篇論文，其中4篇SCI期刊論文，4篇EI會議論文，包括CCF A類會議論文。申請專利一項，出版專著一部，基本達到了立項之初的要求和目的。
