大规模图数据的高效计算关键技术研究(精)/清华大学优秀博士学位论文丛书

由于具有良好的表达能力，图数据结构被广泛用来对元素间具有复杂联系的数据进行建模，如社交网络、知识图谱等。因此，可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究话题之一。目前，已有为数众多的图计算系统被提出和应用，并取得了巨大的商业成功。本书通过将不同环境下图计算系统的数据载入途径分为四个阶段分别进行了研究，总结出了一系列的优化方法，可为相关研究人员提供参考。

第 1章引言 1 1 1大规模图计算 1 1 2图计算系统的分类 2 1 3图数据高效计算的挑战 5 1 3 1图计算的特点 6 1 3 2现状和主要优化方向 7 1 4主要贡献 9 1 5本书组织结构 11 第 2章相关工作 13 2 1基于分布式集群的图计算系统 13 2 1 1分布式图计算中的基本概念 13 2 1 2分布式图计算中任务的划分算法 15 2 2基于外存的图计算系统 18 2 2 1外存图计算系统的意义和挑战 18 2 2 2以点为中心的外存图计算系统 20 2 2 3以边为中心的外存图计算系统 21 2 3基于矩阵的图计算引擎 23 2 4基于存算融合硬件的图计算系统 26 第 3章分布式图计算系统的三维任务划分 31 3 1概述 31 3 2实例研究：协同过滤问题 33 3 3三维划分的基本概念 34 3 4三维划分下的编程模型 37 3 4 1数据模型 37 3 4 2 UPPS下的三维划分 39 3 4 3计算模型 40 3 4 4二部图 41 3 4 5与 GAS模型的比较 41 3 4 6例程 42 3 5系统实现 47 3 5 1数据载入和划分 47 3 5 2 Update操作的实现 48 3 5 3 Push，Pull和 Sink操作的实现 49 3 5 4基于矩阵的数据结构 49 3 6实验结果 50 3 6 1测试环境 51 3 6 2微型测试集 52 3 6 3实际应用 57 3 6 4其他讨论 62 3 7小结 66 第 4章外存图计算系统的分层数据组织 67 4 1概述 67 4 2背景介绍 69 4 2 1外存图计算系统中的一维划分： GraphChi 69 4 2 2外存图计算系统中的二维划分： GridGraph 70 4 3 3DGridGraph 72 4 3 1分层存储优势 72 4 3 2编程模型 74 4 3 3实例研究 75 4 3 4实现 76 4 4测试结果 77 4 4 1定量分析 77 目录 15 4 4 2实测结果 78 4 5小结 79 第 5章矩阵计算引擎的自动优化 81 5 1概述 81 5 1 1背景介绍 81 5 1 2挑战 82 5 1 3我们的工作 83 5 2设计思路与原理 84 5 3 Kasen的编程模型 86 5 3 1数据 86 5 3 2数据的操作 87 5 3 3实例： PageRank 89 5 3 4应用范围 90 5 4 Kasen模型的具体实现 91 5 4 1三种数据存储状态 91 5 4 2显式的存储状态转化 93 5 4 3约束条件 94 5 5优化方法 96 5 5 1循环融合 96 5 5 2内部操作 98 5 5 3 DDAG 100 5 5 4优化算法 101 5 5 5实例研究 104 5 6估算公式 105 5 7实现细节 107 5 8性能测试 108 5 8 1定量分析 108 5 8 2性能测试 110 5 8 3与已有系统的性能对比 112 5 9小结 113 第 6章拓扑感知的存算融合图计算方法 115 6 1概述 115 6 2背景介绍 118 6 2 1互联拓扑结构 118 6 2 2网络瓶颈 120 6 2 3已有的 PIM图计算系统 121 6 3 PGIM系统 123 6 3 1两阶段点程序 123 6 3 2广播 128 6 3 3计算和通讯的重合 129 6 4测试 129 6 4 1划分对通讯量的影响 130 6 4 2广播对瓶颈链路通讯量的影响 131 6 5小结 131 第 7章总结与展望 133 7 1总结 133 7 2展望 134 参考文献 137 在学期间发表的学术论文与研究成果 145 致谢 147