大規模圖數據的分散式處理

《大規模圖數據的分散式處理》是2015年清華大學出版社出版的圖書，作者是谷峪、於戈、鮑玉斌。

基本介紹

• 書名：大規模圖數據的分散式處理
• 作者：谷峪、於戈、鮑玉斌
• 出版社：清華大學出版社
• 出版時間：2015年12月01日
• 定價：58 元
• ISBN：9787302420729

內容簡介

隨著以社交網路為代表的圖數據規模高速增長，複雜的查詢需求不斷湧現，處理這類大規模數據有許多理論問題需要解決。本書結合作者多年的研究積累，系統地介紹了大圖分散式處理中基礎的數據劃分、組織和訊息管理技術，以及三角形、最大k邊連通子圖、最小生成樹、頻繁子圖、重疊社區發現等大圖查詢和分析算法的最佳化，並對系統實現技術進行了探討。 本書適合高等院校計算機專業的教師、學生及計算機套用系統的研發人員閱讀參考。本書封面貼有清華大學出版社防偽標籤，無標籤者不得銷售。

圖書目錄

第1章大規模圖數據處理：問題與挑戰

1.1大圖數據處理的背景

1.2圖數據的表示

1.3傳統的大圖數據管理方法

1.4雲計算環境處理大圖數據的優勢

1.5新型大圖計算系統面臨的挑戰

1.6關鍵技術問題

第2章大圖分散式處理的計算模型和執行機制

2.1大圖分散式處理的基本計算框架

2.1.1基於MapReduce的計算框架

2.1.2基於BSP的計算框架與GAS模型

2.1.3MapReduce與BSP對比

2.1.4其他處理框架

2.2圖查詢處理的遍歷模式

2.2.1以頂點為中心

2.2.2以子圖為中心

2.2.3以邊和路徑為中心

2.3訊息通信

2.3.1訊息傳送時序控制

2.3.2訊息交換模式

2.3.3網路通信平台

2.3.4上層訊息最佳化技術

2.4同步控制

2.4.1同步模式

2.4.2異步模式

2.4.3混合模式

2.4.4跨步模式

2.5容錯管理

2.5.1故障恢復技術

2.5.2故障偵測技術

2.6任務調度

2.7可擴展性

第3章大圖數據劃分技術

3.1圖數據劃分技術綜述

3.1.1離線劃分算法

3.1.2線上劃分算法

3.1.3動態劃分算法

3.2大圖劃分定義

3.2.1處理流程和定義

3.2.2真實圖的局部性分析

3.3OnFlyP劃分算法

3.3.1Range劃分

3.3.2OnFlyP劃分

3.3.3負載均衡控制機制

3.3.4計算接口描述

3.3.5動態調整機制

3.4性能評價

3.5小結

第4章大圖數據分散式存儲與索引技術

4.1大圖數據的存儲索引技術綜述

4.2圖疊代算法的狀態轉換模型

4.3大圖的磁碟存儲管理機制

4.3.1基於列存儲模型的靜態Hash索引策略

4.3.2基於狀態轉換的動態Hash索引策略

4.4基於訊息有序的磁碟疊代

4.4.1訊息有序疊代MSI

4.4.2OERSV數據模型

4.4.3兩階段計算過程

4.5性能評價

4.6小結

第5章大圖數據分散式三角形查詢技術

5.1大圖三角形查詢技術綜述

5.1.1集中式算法

5.1.2分散式算法

5.1.3近似算法

5.2分散式大圖三角形查詢最佳化技術

5.2.1存儲結構

5.2.2ENIterator算法

5.2.3訊息最佳化

5.3基於採樣的近似處理技術

5.3.1採樣策略

5.3.2算法描述

5.4性能評價

5.5小結

第6章大圖數據分散式最大k邊連通子圖查詢技術

6.1大圖最大k邊連通子圖查詢技術綜述

6.2分散式最大k邊連通子圖最佳化技術

6.2.1頂點最佳化

6.2.2剪枝策略

6.2.3訊息最佳化

6.3基於採樣的近似處理技術

6.3.1採樣策略

6.3.2算法描述

6.4性能評價

6.5小結

第7章大圖數據分散式最小生成樹查詢技術

7.1大圖數據最小生成樹綜述

7.2頂點驅動的並行MST算法

7.2.1PB算法(分區Prim算法+Borvka算法)

7.2.2算法正確性

7.2.3雙重索引

7.2.4終止條件

7.2.5索引維護

7.3基於並行處理模型的PB算法

7.3.1基於MapReduce模型的PB算法

7.3.2基於BSP模型的PB算法

7.3.3PB算法代價分析

7.4動態圖的MST維護算法

7.4.1MST結果預處理

7.4.2刪除邊維護

7.4.3刪除頂點維護

7.4.4維護代價

7.5性能評價

7.6小結

第8章大圖數據分散式頻繁子圖挖掘技術

8.1圖數據頻繁子圖挖掘技術綜述

8.1.1圖數據集中的頻繁模式挖掘算法

8.1.2單個大圖的頻繁模式挖掘算法

8.1.3並行圖頻繁模式挖掘

8.2基於最大團頻繁計數的頻繁子圖挖掘

8.2.1整體框架

8.2.2挖掘頻繁1子圖

8.2.3候選子圖產生

8.2.4頻繁計數

8.3頻繁子圖挖掘分散式處理的最佳化

8.4基於AMNI頻繁計數的子圖挖掘

8.5頻繁子圖挖掘的BSP實現

8.6性能評價

8.7小結

第9章大圖數據分散式重疊社區發現技術

9.1複雜網路重疊社區發現技術綜述

9.1.1團滲透方法

9.1.2邊圖與邊劃分方法

9.1.3局部擴展最最佳化算法

9.1.4模糊檢測法

9.1.5基於混合機率模型算法

9.1.6基於非負矩陣分解算法

9.1.7其他類型算法

9.2分散式並行極大團枚舉

9.2.1問題描述

9.2.2極大團枚舉方法

9.2.3極大團枚舉方法最佳化

9.2.4並行極大團枚舉方法

9.2.5複雜度分析

9.3複雜網路中並行重疊社區發現

9.3.1問題描述

9.3.2GCE基本算法

9.3.3GCE算法的最佳化

9.3.4GCE算法並行化

9.4性能評價

9.5小結

第10章大規模圖數據分散式處理系統和套用

10.1基於MapReduce模型的大圖處理系統

10.1.1PEGASUS

10.1.2HaLoop

10.1.3Twister

10.2基於BSP模型的大圖處理系統

10.2.1Pregel

10.2.2Hama

10.2.3Giraph

10.2.4Giraph++

10.2.5GPS

10.2.6XPregel

10.2.7Pregelix

10.2.8MOCgraph

10.2.9Kylin

10.3其他代表性系統

10.3.1PowerGraph

10.3.2Trinity

10.3.3GBase

10.3.4Spark(GraphX)

10.3.5GraphLab

10.3.6Chronos

10.3.7LFGraph

10.3.8GraphChi、XStream和TurboGraph

10.4BCBSP系統介紹

10.4.1體系結構概況

10.4.2圖處理作業的執行流程

10.4.3PageRank算法示例

10.5大規模圖數據分散式處理的套用

10.5.1Web套用

10.5.2社會網路套用

10.5.3生物和化學領域套用

參考文獻

前言

數據能夠有效地反映數據之間普遍存在的聯繫，具有豐富的表達力，在Web、社會網路、生物和化學資料庫等領域獲得了廣泛的套用。隨著數據獲取方式的多樣化，圖數據規模越來越大，套用也日趨複雜，傳統的集中式圖查詢處理和分析挖掘方法滿足不了日益增長的功能和性能上的需求。特別是近年來隨著雲計算和大數據等概念的興起，分散式圖處理計算也隨之得到快速的發展，成為熱點的研究領域。本專著系統綜述了目前該領域的主要研究進展，並總結和整理了作者近年來在這方面的研究成果，內容囊括大規模圖數據分散式處理的主要模型、技術和系統，包括執行機制、數據組織、代表性算法，以及系統實現和典型套用等各個方面。本書試圖為讀者系統地展現大數據技術高速發展和變革時代大圖處理區別於傳統數據管理和分散式計算的新技術、新思想、新系統和新挑戰。

本書共分為10章，第1章主要介紹大規模圖數據分散式處理的研究背景和問題；第2章介紹分散式圖計算模型和執行機制；第3章和第4章分別介紹基礎的數據組織問題，包括數據的劃分以及存儲和索引；第5章到第9章介紹代表性的大圖複雜查詢、分析和挖掘算法及其分散式實現技術，包括三角形查詢、最大k邊連通子圖查詢、最小生成樹搜尋、頻繁子圖挖掘和重疊社區發現；第10章對現有的主要分散式大圖處理系統和典型套用進行綜述。

本書涉及的研究課題得到國家重點基礎研究發展計畫項目、國家自然科學基金項目、教育部中國移動科研基金項目等資助。

作者指導的部分研究生參與了本書的撰寫和相關課題的研發，他們是王志剛、劉金鵬、王文安、楊佳學、張天明、張楠、畢亞輝等，他們為本書付出了辛勤的勞動，在此一併表示衷心的感謝。

該專著主要作為從事圖數據管理、分散式計算和大數據分析等相關領域研究開發和管理人員的參考書籍，也可作為高校計算機和大數據等相關專業研究生的補充教材和參考讀物。

由於著者水平所限，而本書涉及很多新的技術，因此書中難免有疏漏和錯誤，懇請讀者提出寶貴意見。

作者

2015年5月7日