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

作     者：张雕 

作者单位：上海交通大学 

学位级别：硕士

导师姓名：梁阿磊

授予年度：2015年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：大规模图 图计算平台 云计算 图算法 图表示 

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