基于图算法与最佳图表示的单台PC图计算平台研究

摘要

图可以描述实体与实体之间的联系，以顶点和边的抽象的方式分析现实中的问题，如好友推荐、网页排名PageRank。传统的图算法假设整个图数据可以加载进单台 PC内存，所以对于大规模图，如社交网络、互联网等无法处理。云计算以及分布式图算法的研究用于大规模图的处理，如Hadoop，从扩展性、容错以及开源可用性等方面发挥优势，但仍存在控制与可靠性、数据安全、成本花费以及分布式图算法的调试与优化较难的问题。
　　针对这种情况，学术界开始研究如何使用单台 PC进行大规模图数据的处理，并达到较之于分布式算法的合理时间消耗。现有的基于单台 PC的图计算平台，如 GraphChi、TurboGraph，已经可以进行大规模图数据的处理。但是从平台计算性能和易用性(即基于平台进行图问题的抽象)两方面都存在可以优化的方面。
　　本文基于对图算法与最佳图表示、CPU与I/O并行性以及内存利用三方面的研究，在GraphChi基础上设计和实现了一个基于单台PC的图计算平台HybridGraph，使计算性能和算法抽象两部分得到改进。
　　本文的主要工作包括：（I）研究和分析了图算法表示，以及总结出与图算法最佳匹配的图表示方法；（II）探索并证明了通过图算法与图表示格式的匹配可以提高图处理效率；（III）基于开源图计算平台GraphChi，实现了HybridGraph图计算平台。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1课题研究背景

1.2相关研究现状

1.3本文内容安排

第二章 图与图算法

2.1引言

2.2图的基本概念

2.3图算法

2.4本章小结

第三章 单台PC图计算平台HybridGraph的设计

3.1引言

3.2 GraphChi分析

3.3单机图计算平台设计思路

3.4图计算配置管理

3.5图数据预处理

3.6图计算引擎

3.7本章小结

第四章 单台PC图计算平台HybridGraph的实现

4.1引言

4.2 HybridGraph API实现

4.3图计算配置管理实现

4.4图数据预处理实现

4.5图计算引擎实现

4.6本章小结

第五章 实验与分析

5.1引言

5.2实验环境介绍

5.3实验算法

5.4实验数据集介绍

5.5实验结果与分析

5.6本章小结

第六章 结束语

6.1主要工作与创新点

6.2后续研究工作

参考文献

致谢

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

上海交通大学硕士学位论文答辩决议书