图计算系统简介
GeminiGraph
分布式、In Memory, 提供Vertex-centric编程模型。
-
Schema
- 在内存中采用（双压缩稀疏列、行）DCSR、DCSC结构来存储图数据。
-
分区
- Locality-aware chunking：从顶点访问局部性和任务量角度来划分机器间顶点的分区，实现计算负载均衡。
- Numa-aware Sub-partition：采用Numa感知方式来对机器中分区数据进一步分区，从减少remote access角度来提升计算效率。
-
计算方面
- 通过提供Push、Pull两种计算模式来减少竞争操作，根据活跃边集和总边数的比例设定的阀值来自动切换不同模式。（多轮迭代间会采用不同的模式，一轮迭代中只会采用一种模式）
- 采用chunk-based work-stealing：采用偷任务的方式让计算能力得到充分利用。
发表会议：OSDI Conference 2016
作者导师：清华，陈文光
Venus（无源码）
- 单机、out-of-core, Vertex-centric编程模型(只提供顶点的入边)
- 基于边流式计算
发表会议：ICDE Conference 2015
作者：香港中文大学，刘勤
GraphChi
单机核外、Vertex-centric编程模型，计算过程支持图的动态变化
Ligra
单机内存、Vertex-centric编程模型
GridGraph
单机核外、Edge-centric编程模型
NXgraph(无源码)
单机核外、Edge-centric编程模型
G-Miner
分布式，out-of-core, subgraph-centric计算模型。专为解决Graph mining类算法而设计。
发表：Eurosys Conference 2018
作者导师简介：香港中文大学:James Cheng
三种编程模型
- 图计算编程模型包括edge-centric、vertex-centric和 subgraph-centric编程模型，三种各有优缺点。
edge-centric编程模型
其支持的图算法要满足如下性质：
v_dst = f( v_src1, v_src2, v_dst ) = f( v_src2, f(v_src1, v_dst) )
即依次处理每条边得到partial result可以得到最终的计算结果
- 而在需要获得所有邻居节点的图算法（如LPA、CD、Graph Coloring等）中，采用edge-centric编程模型无法实现。
vertex-centric编程模型
其可以实现所有图算法，但是在一些算法上没有edge-centric模型实现的算法效率高（比如：ALS协同过滤）
- 目前大多数系统都是提供这种编程模型，所以在算法参考和移植上相对容易。
subgraph-centric
适合Graph mining类算法
图数据库
- JanusGraph：集成了图计算和图存储，支持gremlin查询。
相关阅读：Venus | 图计算系统进展和展望
TP和AP结合的图数据库
图数据集
J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks.Journal of Machine Learning Research,11(Feb):985{1042, 2010.
