| 失效链接处理 |
|
大规模图数据的高效计算 PDF 下载
本站整理下载：
相关截图：
主要内容：
1.1 大规模图计算
随着计算机技术的不断发展，其应⽤范围逐渐推⼴到⼈类⽣产⽣活的⽅⽅⾯
⾯。当前被计算机系统产⽣或者收集到的数据的规模正在飞速增长，这些⼤规模
数据的存在⽆疑对现代计算机系统的⼤规模数据存储、管理、乃⾄于分析处理的
能⼒提出了极其尖锐的挑战。为了应对这⼀挑战，以⾕歌和微软为代表的各⼤公
司以及诸多的学术界团队提出了⼀系列的⼤数据处理系统[1–5]。这些系统通过横向
以及纵向扩展的⽅式极⼤地提升了数据处理系统的处理效率，扩展了它们所能承
载的最⼤数据规模。
作为⼤数据中重要的⼀类，大规模图数据的管理与分析是近来备受重视的⼀
个热点话题。举例⽽⾔，近来发展迅猛的各类社交⽹络就天然地产⽣了⼀个个规
模巨⼤的图数据集。根据⼀项近期的统计结果[6]，Facebook 公司所维护的社交⽹
络拥有将近⼆⼗亿的⽤户。如果以图的模型进⾏建模，其结果将会拥有近⼆⼗亿
个点（代表各个⽤户）以及更⾼数量级的边（⽤于描述⽤户间的关系）。⽀持在这
样规模的图上进⾏⾼效地查询和分析的需求⽆疑是现有系统所需应对的⼀项重要
挑战。同时，由于图这⼀数据结构的灵活性，许多原本通过稀疏矩阵等其他数据
结构进⾏建模的问题往往也都可以转化成图计算的形式。因此，正如我们将在后
⽂第 3.2 节中详细描述的，诸如协同过滤等在内的很多机器学习和数据挖掘算法
也都被认为是涵盖在图计算系统的处理范围之内的。这⼀现象极⼤地拓展了图计
算的应⽤范围，因此也间接地提升了图计算系统的重要性。
鉴于⼤规模图数据的普遍存在以及对其进⾏分析处理的实际需求，众多商业
公司和学术团队设计和提出了⼀系列的⼤规模图计算系统[1–4]。与传统的数据并⾏
类⼤数据处理系统（如 MapReduce[7]，Spark[8] 等）不同，这些专⽤图计算系统专门
针对图这⼀数据结构本⾝的特点进⾏了优化，从⽽避免了传统通⽤系统在图这⼀
类数据间具有复杂联系的数据上可扩展性不好的问题。经过最近数年的发展，⽬
前的⼤规模图计算系统已经具有了极⾼的可扩展性。根据 Facebook 公司研究⼈员
的报告，他们通过将 Giraph[9] 系统横向扩展到数百台机器之上成功地对包含数⼗
亿条边的超⼤规模图数据集进⾏了处理。与此同时，由于点程序（Vertex Program）
等简单有效的编程接⼜的提出，程序员们可以⾮常简单地进⾏图计算的编程⽽⽆
需考虑⽹络通讯、外存访问等复杂问题。往往系统可以⼏乎完全⾃动地将⽤户编
写的单机单进程程序扩展到多核乃⾄多机环境下，甚⾄可以⾃动地进⾏单点容错。
1
第 1 章 引⾔
由此可见，在可扩展性和易⽤性等⽅⾯⽬前已有的研究已经取得了⾮常良好的结
果。也正是因为这样的原因，⽬前图计算系统已经被部署在众多的商业公司之中
⽤于⽀撑它们的多种关键业务[6]。
1.2 图计算系统的分类
利⽤图对问题进⾏建模和计算是⼀门古⽼的数学分⽀，其历史最早可以追溯
到欧拉于 1736 年对著名的哥尼斯堡七桥问题的论述，⽐第⼀台通⽤计算机的诞⽣
时间还要早⼤约两百年。同时，由于图这⼀数据结构天然适合于研究⽤某种⽅式
联系起来的若⼲事物之间的⼆元或多元关系，⼀经提出图计算就⼀直是热点研究
⽅向之⼀。在计算机研究⽅⾯，各式的图论算法（如最短路径、最⼩⽣成树）和其
它通过图进⾏建模的机器学习和数据挖掘算法（如 PageRank，聚落挖掘）都被⼴
泛地应⽤于⽣产⽣活的⽅⽅⾯⾯，产⽣了巨⼤的价值[10]。然⽽，随着“⼤数据”时代
的到来，⽬前被收集到并希望⽤计算机系统分析处理的图数据的规模正以极⾼的
速度不断增长。如上⼀节中提到的 Facebook 社交⽹络的例⼦，⽬前需要计算的图
数据的规模往往⾼达数百数千万、乃⾄上亿条边的级别。在这种情况下，传统的单
机全内存图计算系统的计算性能和数据容量就变得不再能满⾜实际的需求。因此，
⽬前有很多的新技术新⽅法被⼯业界和学术界的研究⼈员提出，⽤于搭建⼤规模
图数据的处理系统。
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
