论文总字数：54219字

摘 要

当今世界因互联网的快速发展而更加融合，其中社交网络、在线交易等产生的数据呈现爆炸式的增长，且其大部分数据是以图的形式存在。图作为一种表达不同数据实体之间关系的数据结构得到广泛的应用，但日益丰富庞大的图数据为图分析带来了巨大的困难。近年来随着Pregel系统的提出，出现了两类图处理系统来解决这一困难。而实际应用领域内，对于解决相同问题的各种系统之间的实验评估和比较是一项至关重要的工作。

本文对基于Datalog的大数据图处理系统与通用大数据图处理系统从理论分析和实际实践层面进行评估和对比，来量化它们的优点，并明确各自的局限性。本文的主要研究内容包含以下三个方面：

(1)理论分析。对通用大数据图处理系统从编程模型等七个方面进行展开分析，对基于Datalog的系统从系统框架等三个方面展开分析，以此来阐述各自系统处理图计算时的特点和不同点。

(2)性能对比实验。通过选取合适的图分析算法、图数据集以及评价指标，并在各系统上执行计算。实验结果表明，通用大数据图处理系统的性能要优于基于Datalog的大数据图处理系统。

(3)应用难易对比实验。通过对比在各系统实现图分析算法所需的代码行数，来反应各系统在图分析算法应用上的难易程度。实验结果表明，基于Datalog的系统实现图分析算法所需代码行数更少，表达图分析算法更加简洁直观。

通过结合上述工作，本文从高层次编程模型、复杂工作流和动态图分析等角度分析了图处理系统领域现阶段面临的挑战。

关键词：大数据图，图处理系统，Datalog，图分析算法

Abstract

Nowadays, the whole world is becoming more integrated due to the rapid development of the Internet, in which the data generated by social networks, online transactions and so on has shown explosive growth, and most of the data exist in the form of graph. Graph is widely used as a kind of data structure to represent the relationship between different data entities, however, the increasing abundance of graph data brings great difficulties to graph analysis. In recent years, with the proposal of Pregel system, two types of graph processing systems have emerged to solve this problem. And in the field of realistic applications of computer science, it’s a crucial work to evaluate and compare the experiments among different systems to solve the same problem.

In this thesis, the Datalog based graph processing system and the general purposed graph processing system are evaluated and compared from the theoretical analysis and practical level, so as to quantify their advantages and clarify their limitations. The main research content of this thesis includes the following three aspects:

(1) Theoretical analysis. The general purposed graph processing system is analyzed from seven aspects, including programming model and so on, while the Datalog based system is analyzed from three aspects, including framework and so on. It aims to explain the characteristics and differences of each system in graph processing.

(2) Performance comparison. By choosing appropriate graph analysis algorithms, graph datasets, and evaluation indexes, the calculation is carried out on each system. The experimental results show that the performance of the general purposed graph processing system is better than the Datalog based system.

(3) Comparison of application difficulty. Through statistical comparison of the number of lines of code to implement the graph analysis algorithms for each system, therefore it can reflect the difficulty of the application the graph analysis algorithms in each system. The experimental results show that the Datalog based system needs fewer lines of code to implement graph analysis algorithms, and the expression of graph analysis algorithms is more concise and intuitive.

Based on the above work, this thesis analyzes the current challenges in the graph processing system from the perspectives of high-level programming model, complex workflows and dynamic graph analysis.

KEY WORDS: Large scale graph, Graph processing system, Datalog, Graph analysis algorithm.

目 录

摘要 I

Abstract II

第一章 绪论 1

1.1 研究背景 1

1.2 国内外研究现状 2

1.2.1 通用大数据图处理系统的研究进展 2

1.2.2 基于Datalog的大数据图处理系统的研究进展 4

1.3 研究目标与内容 5

1.4 论文结构与安排 5

第二章 相关知识介绍 7

2.1 图 7

2.2 图系统一般执行框架 7

2.2.1 读入/写回数据阶段 7

2.2.2 预处理阶段 8

2.2.3 数据分区阶段 8

2.2.4 执行计算阶段 8

2.3 图分析算法 8

2.3.1 图遍历算法 8

2.3.2 图匹配算法 9

2.3.3 社区发现算法 9

2.3.4 连通分量算法 9

2.3.5 中心度量算法 9

2.4 Datalog 9

2.5 本章小结 11

第三章 基于Datalog的大数据图处理系统与通用大数据图处理系统理论分析 12

3.1 通用大数据图处理系统对比分析 12

3.1.1 系统体系架构 12

3.1.2 编程模型 14

3.1.3 执行计算模型 16

3.1.4 分区策略 18

3.1.5 通信机制 19

3.1.6 存储机制 20

3.1.7 容错处理 21

3.2 基于Datalog的大数据图处理系统对比分析 22

3.2.1 系统实现框架 22

3.2.2 Semi-Naïve Evaluation的实现 23

3.2.3 Datalog引擎的优化 24

3.3 本章小结 27

第四章 实验结果及分析 28

4.1 实验环境 28

4.2 实验数据 28

4.2.1 实验数据集 28

4.2.2 数据格式转换 29

4.3 实验图分析算法 30

4.3.1 实验图分析算法的选择 30

4.3.2 实验图分析算法的设计与实现 31

4.4 实验评价指标 39

4.4.1 预处理时间 39

4.4.2 执行计算时间 39

4.4.3 总处理时间 39

4.4.4 LOC 39

4.5 实验结果及分析 40

4.5.1 每种算法在不同系统不同数据集上的性能对比 40

4.5.2 应用难易对比 47

4.6 本文对当前大数据图处理系统分析的结论 48

4.7 本章小结 49

第五章 总结与展望 50

5.1 工作总结 50

5.2 未来工作展望 50

参考文献 52

致 谢 54

绪论

研究背景

当前，我们对于人与设备或者其他实体的连接联系比历史上任何一个时期都更加紧密。世界正因互联网的快速发展而变得更加融合，其中社交网络、在线交易、运输网络、移动终端等数据源产生的海量数据，呈现爆炸式的增长趋势。而这其中的很大一部分数据都是以链接的形式存在的，更具体些，是以图的形式存在的。

图作为一种基本的数据结构，能够用来表达不同数据实体之间的关系，如相互作用关系、依赖关系等。在实际中，图被广泛应用于社交网络、运输网络、金融交易网络、计算生物学等不同应用领域的复杂数据建模。

剩余内容已隐藏，请支付后下载全文，论文总字数：54219字