面向图计算内存系统的实现与拓展

刘令斌，任 龙，黄建强，黄东强

(青海大学计算机技术与应用系，青海 西宁 810016)

随着信息技术的高速发展，人类迎来了大数据时代，导致数据规模急剧增长。近几年，Twitter的月活跃用户产生的数据占几百GB甚至TB级别的存储量[1]，现实生活所产生的规模庞大的各种类型的数据，基本都可以抽象为图数据结构(graph-structured data)[2-3]。然而，传统的图计算算法处理大规模图数据具有很明显的缺陷，因此，如何高效处理大规模图数据成为很多研究的重点问题。Ligra是解决此类问题性能最好的图计算系统之一[4]。Beamer等[5]提出了关于遍历方式的优化，Ligra使用这种优化方式，以 广度优先搜索算法(Breadth First Search，BFS)为例，不同于传统的 BFS 算法中由源点到底端的遍历方式，Ligra 通过阈值判断需要遍历的点集是否稀疏——如果稀疏则使用 Top-Down 自上而下的方法进行遍历；如果稠密，则使用 Bottom-Up 自下而上的方法进行遍历，从而解决负载不均衡的问题[6-7]，能高效地使用多线程并行。同时，在大规模图计算领域中，国内外学者通过研究找到了新的优化方向[8-12]。Ligra实现了 BFS、单源最短路径(Single-Source Shortest Path，SSSP)等图计算算法的优化 ，但是支持的图计算算法仍不全面，存在可拓展的空间。

本文通过对 Ligra 进行拓展，实现深度优先搜索算法(Depth First Search，DFS)及子图匹配算法，用来更好地解决传统图计算算法运算速度过慢的问题。

1 图计算系统的实现

1.1 存储格式

表1中以图数据soc-Livejournal为例，展示不同格式下数据大小及获取点的出度所需要的时间。其中，ELL(ELLPACK)格式与邻接矩阵格式需要占用超过50 GB的存储空间；……