基于磁盘的单机大规模图计算引擎性能的改进方法

摘要

本文研究图计算引擎性能问题。现实世界的许多对象都能够被转化成图格式，并且运用各种图处理工具进行高效处理。GraphChi是最先提出能够在单机上高效处理十亿规模节点的基于磁盘的图计算引擎，在性能上能够接近甚至超越那些主流的分布式图计算引擎。
　　本文针对图计算引擎其中的两个方面进行了改进，主要包括两部分：1）图计算引擎的内存管理制度以及2）图计算引擎的算法。
　　在图计算引擎的内存管理制度的问题上，本文受到TurboGraph的“pin”的概念以及GraphLab中“ghost”的概念的启发，提出了一种新的内存管理制度来提高GraphChi引擎的性能。这种模式的主要思想是在整个计算过程中将一部分数据固定在内存里。此改进在原始的GraphChi引擎上仅增添了40行左右的代码，却收获了最高达60％性能的提高。分别运用不同大小的内存、点数据集、边数据集以及放入内存数据比例进行了相应的实验，证明了这种优化模式的通用性及有效性；并且在实验过程中我们发现在整个数据集无法完全放入内存的情况下，存在一个最优的固定到内存的数据比例，此时能够获得最优的性能。
　　在针对图计算引擎处理的算法进行优化上，受到著名的六度空间理论的启发：当某些节点迭代过程中值的变化满足一定条件时，可以停止对这部分相对次要的节点进行计算，这并不会对那部分重要节点造成影响。在大数据集上进行了相关实验，验证了本文提出的优化算法的有效性（最高24%性能的提高）以及准确性；同时通过对节点收敛值以及过滤不同比例的次要节点进行了研究，揭示了它们与图计算引擎性能的密切联系。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题研究目的和意义

1.2 课题研究内容

1.3 主要贡献

1.4 论文组织结构

第二章 国内外研究现状

2.1 国外重要论文研究

2.2 国内论文研究

2.3 技术特点分析与总结

2.4 实验主要算法介绍——PageRank算法

2.5 GraphChi程序运行

2.6 本章小结

第三章 GraphChi及其PSW算法介绍

3.1 GraphChi模型的提出

3.2 PSW算法简介

3.3 GraphChi内存管理的部分局限性

3.4 本章小结

第四章 图计算引擎结合内存管理模式（Part-in-memory）的改进思想及实验分析

4.1 Part-in-memory模式的思想

4.2 Part-in-memory模式的实现

4.3 实验及分析

4.4 本章小结

第五章 图计算引擎结合算法角度的改进思想及实验分析

5.1 六度空间理论优化算法主要思想

5.2 六度空间理论优化算法的实现

5.3 六度空间理论优化算法与原始算法比较

5.4 过滤不同比例数据对图计算引擎的影响

5.5 本章小结

第六章 结论与展望

6.1 结论

6.2 展望

6.3 本章小结

参考文献

致谢

攻读硕士学位期间已发表或录用的论文

声明