图计算系统简介
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 | 图计算系统进展和展望
网友评论