| 引用本文: | 阚忠良,李建中,徐俊,王宏志.基于GPS平台的高效k-bisimulation计算算法[J].哈尔滨工业大学学报,2018,50(5):173.DOI:10.11918/j.issn.0367-6234.201711054 |
| KAN Zhongliang,LI Jianzhong,XU Jun,WANG Hongzhi.GPS-based algorithms for efficient k-bisimulation computation[J].Journal of Harbin Institute of Technology,2018,50(5):173.DOI:10.11918/j.issn.0367-6234.201711054 |
|
| 摘要: |
| 计算图的互模划分在许多应用领域中起着至关重要的作用.图中两个点是互模的当且仅当这两点具有相同的特征.随着图数据规模的增大，传统的运行在单机上的互模划分算法面临着越来越大的挑战，分布式算法以及并行算法则成为提高图计算可扩展性的重要途径.最近研究人员提出两种基于MapReduce计算模型的分布式互模划分算法，算法均计算图的局部互模划分.采用MapReduce计算模型的分布式互模划分算法具有网络通讯代价高昂的问题，每次MapReduce迭代操作均会将整个图中所有点边的状态通过网络传输，重新为点边分配计算节点，但实际上计算点的局部互模划分特征仅需要局部信息.以此为研究出发点，本文提出了基于分布式图数据处理平台的互模划分算法，仅使用点的局部信息来计算其特征，进而提升计算效率.经过实验验证，本文算法可以大幅度减少算法执行过程中的网络数据传输量.在包含数亿边大图上的实验表明，在未经图的预处理的情况下，本文算法的时间效率提升了7~16倍，有效的解决了MapReduce计算模型带来的网络通讯代价高昂的问题.
|
| 关键词: 互模划分 k-互模划分 图处理系统 分布式算法 大数据 |
| DOI：10.11918/j.issn.0367-6234.201711054 |
| 分类号:TP311 |
| 文献标识码:A |
| 基金项目:国家科技支撑计划项目(2015BAH10F01)；国家自然科学基金项目(U6,9) |
|
| GPS-based algorithms for efficient k-bisimulation computation |
|
KAN Zhongliang,LI Jianzhong,XU Jun,WANG Hongzhi
|
|
(1. School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China; 2. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
|
| Abstract: |
| Computing the bisimulation partition of a graph plays a key role in various application areas. Two nodes are bisimular if and only if they obtain the same signature. Faced with a big graph, traditional in-memory algorithms can hardly meet practical need. Recently, researchers have proposed two kinds of MapReduce based distributed algorithms to handle bisimulation partition on the big graph, both calculating localized bisimulation. MapReduce based algorithms suffer from huge network communication burden, at the meantime, we only need local information to calculate the signature of a node. Motivated by these observations, we propose an algorithm based on a graph processing system that only uses local information to calculate the signature of a node. We argue that our algorithm can make considerable reduction on the network transportation during computation. In the experiment calculated on the big graph which contains billions of edges, our algorithm can be seven to sixteen times faster even without graph pre-partition.
|
| Key words: simulation partition k-bisimulation graph processing system distributed algorithms big data |
