基于图算法与最佳图表示的单台PC图计算平台研究-计算机科学与技术专业论文.docx

万方数据 万方数据 上海交通大学 学位论文原创性声明 本人郑重声明:所呈交的学位论文《基于网络操作系统的负载均 衡应用框架设计)) ，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献 的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明 的法律结果由本人承担。 学位论文作者签名:极推 日期:JOü;:年 l 月 /3 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 (请在以上方框内打 .J ) 学位论文作者签名:张啦 日期: 2oJ5 年 l 月/主日 三久，/ 指导教师签名 : V 机--í 日期:刻5 年/月 13日 上海交通大学硕士学位论文 上海交通大学硕士学位论文 万方数据 万方数据 基于图算法与最佳图表示的单台 PC 图计算平台研究 摘要 图可以描述实体与实体之间的联系，以顶点和边的抽象的方式分 析现实中的问题，如好友推荐、网页排名 PageRank。传统的图算法假 设整个图数据可以加载进单台 PC 内存，所以对于大规模图，如社交 网络、互联网等无法处理。云计算以及分布式图算法的研究用于大规 模图的处理，如 Hadoop，从扩展性、容错以及开源可用性等方面发挥 优势，但仍存在控制与可靠性、数据安全、成本花费以及分布式图算 法的调试与优化较难的问题。 针对这种情况，学术界开始研究如何使用单台 PC 进行大规模图 数据的处理，并达到较之于分布式算法的合理时间消耗。现有的基于 单台 PC 的图计算平台，如 GraphChi、TurboGraph，已经可以进行大 规模图数据的处理。但是从平台计算性能和易用性(即基于平台进行图 问题的抽象)两方面都存在可以优化的方面。 本文基于对图算法与最佳图表示、CPU 与 I/O 并行性以及内存利 用三方面的研究，在 GraphChi 基础上设计和实现了一个基于单台 PC 的图计算平台 HybridGraph，使计算性能和算法抽象两部分得到改进。 本文的主要工作包括：（I）研究和分析了图算法表示，以及总结 出与图算法最佳匹配的图表示方法；（II）探索并证明了通过图算法与 图表示格式的匹配可以提高图处理效率；（III）基于开源图计算平台 GraphChi，实现了 HybridGraph 图计算平台。 关键词：大规模图、图计算平台、云计算、图算法、图表示 I A Research on Graph Computation Platform in a Single PC by Application of Graph AlgorithmTuned Graph Representation Format ABSTRACT Graph can be used to describe the connenction between entities, and analyze real-world problem, such as friend recommendation and web page ordering, by abstracting entity as vertex and connencion as edge. Tranditional graph algorithms assume the input graph fits in the memory of a single machine. However, the large-scale graphs, such as Web Graph and Social Network, break the assumption. Then, we naturally turn to cloud computing and distributed graph algorithms, such as Hadoop, for their scalability, ease of accessibility and fault tolerance. While the problems of cloud computing remain to be solved, such as control and reliability, data security, unpredicted cos