SpecGraph:基于并发更新的分布式实时图计算模型

被引：5

作者：

景年强

薛继龙

曲直

杨智

代亚非

机构：

[1] 北京大学信息科学技术学院计算机科学与技术系

来源：

计算机研究与发展 | 2014年 / S1期

关键词：

图处理系统; 分布式系统; 实时计算; 并发更新; 推测执行;

D O I：

暂无

中图分类号：

TP391.3 [检索机];

学科分类号：

080201 [机械制造及其自动化];

摘要：

随着互联网的快速发展,越来越多的应用需要在大规模图结构数据上作分析和计算,面对动态变化的图结构,人们希望能够实时地得到反映最新图结构的计算结果.传统的图处理系统都是面向静态图结构,不能满足动态图结构的实时性要求.已经提出的增量图计算模型,其算法适用范围受限,而且都是基于串行执行增量更新,当图结构变化比较迅速时,往往结果的实时性不够高.提出了一种新的基于并发更新的图计算模型SpecGraph,它通过解耦合的计算模型、异步执行引擎和基于推测执行的并发更新机制,达到更广的算法适用性和更高的实时性要求.SpecGraph通过解耦合的计算模型,使得顶点状态只依赖于接收到的邻居信息,为增量更新和并发更新提供了透明实现的可能;通过异步计算引擎,使得系统在增量更新时更加灵活,资源占用低,同时保证了并发的可执行性;通过基于推测执行的并发增量更新,SpecGraph能够达到更高的实时性要求.

引用

页码：155 / 160

页数：6