文档章节

论文阅读 - Thinking Like a Vertex: A Survey of Vertex-

wdfnst
 wdfnst
发布于 2016/05/14 19:52
字数 1610
阅读 21
收藏 0
点赞 2
评论 0

**Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing **ROBERT RYAN MCCUNE, TIM WENINGER, and GREG MADEY, University of Notre Dame

  • Highlight, page
    implements user- defined programs from the perspective of a vertex rather than a graph

  • Highlight, page
    interdependencies

  • Highlight, page
    However, for sequential graph algorithms, which require random access to all graph data, poor locality and the indivisibility of the graph structure cause time- and resource-intensive pointer chasing between storage mediums in order to access each datum.

  • Highlight, page
    MapReduce does not natively support iterative algo- rithms

  • Highlight, page
    identifying the tradeoffs in component implementations and providing data-driven discussion

  • Highlight, page
    subgraph-centric, or hybrid, frameworks

  • Highlight, page
    Think-like-a-vertex frameworks are platforms that iteratively execute a user-defined program over vertices of a graph.

  • Highlight, page
    Many graph problems can be solved by both a sequential, shared-memory algorithm and a distributed, vertex-centric algorithm.

  • Highlight, page
    TLAV frameworks are highly scalable and inherently parallel, with manage- able intermachine communication.

  • Highlight, page
    a given vertex to all other vertices in a graph

  • Highlight, page
    This algorithm, considered a distributed version of Bellman-Ford [Lynch 1996], is shown in Algorithm 1.

  • Highlight, page
    respective edge

  • Highlight, page
    detailing

  • Highlight, page
    proceeds

  • Highlight, page
    Communication

  • Highlight, page
    vertex program execution

  • Highlight, page
    interdependent

  • Highlight, page
    thorough understanding

  • Highlight, page
    interrelation

  • Highlight, page
    a sequential presentation

  • Highlight, page
    discussed earlier.

  • Highlight, page
    conceptually simple

  • Highlight, page
    the overhead becomes largely amortized for large graphs.

  • Underline, page
    synchronous systems are often implemented along with message-passing communication

  • Highlight, page
    batch messaging

  • Highlight, page
    low computation-to-communication ratio

  • Underline, page
    synchronization

  • Underline, page
    accounted for over 80% of the total running time [Chen et al. 2014a],

  • Highlight, page
    underutilized

  • Highlight, page
    the curse of the last reducer

  • Highlight, page
    straggler

  • Highlight, page
    lightweight

  • Highlight, page
    straggler

  • Highlight, page
    outperform

  • Highlight, page
    Theoretical and empirical research

  • Highlight, page
    One disadvantage, however, is that asynchronous execution cannot take advantage of batch messaging optimizations

  • Highlight, page 1
    at the expense of added complexity, not only from scheduling logic, but also from maintaining data consistency. Asynchronous systems typically implement shared memory

  • Highlight, page 1
    pseudo-supersteps [Chen et al. 2014a]

  • Highlight, page 1
    dynamic scheduling within a sin- gle superstep [Wang et al. 2013].

  • Highlight, page 1
    reduces the number of su- persteps by decoupling intraprocessor computation from the interprocessor commu- nication and synchronization [Chen et al. 2014a].

  • Highlight, page 1
    P++ framework [Zhou et al. 2014]

  • Underline, page 1
    boundary nodes

  • Highlight, page 1
    local nodes

  • Highlight, page 1
    pseudo-supersteps

  • Highlight, page 1
    GraphHP and P++, is the KLA paradigm [Harshvardhan et al. 2014]

  • Highlight, page 1
    KLA

  • Highlight, page 1
    is allowed for a certain number of levels before a synchronous round

  • Highlight, page 1
    KLA has multiple traversals of asyn- chronous execution before coordinating a round of synchronous execution

  • Highlight, page 1
    GRACE exposes a programming interface that, from within a given superstep, allows for prioritized exe- cution of vertices and selective receiving of messages outside of the previous superstep.

  • Highlight, page 1
    Motivated by the necessity for execution mode dynamism

  • Highlight, page 1
    PowerSwitch’s heuristics can accurately predict throughput

  • Highlight, page 1
    data for one process is directly and immediately accessible by another process

  • Underline, page 1
    In the case of the former

  • Highlight, page 1
    Otherwise

  • Highlight, page 1
    is flushed when it reaches a certain capacity, sending messages over the network in batches

  • Highlight, page 1
    Shared memory avoids the additional memory overhead constituted by messages and doesn’t require intermedi- ate processing by workers.

  • Highlight, page 1
    Chandy-Misra locking

  • Highlight, page 1
    derivative with

  • Highlight, page 1
    prioritized execution and low communication overhead

  • Highlight, page 1
    Cyclops is a synchronous shared-memory framework [Chen et al. 2014b]

  • Highlight, page 1
    a third method called active messages is implemented in the GRE framework [Yan et al. 2014b].

  • Highlight, page 1
    Within the GRE architecture, active messages combine the process of sending and receiving messages, removing the need to store an intermediate state, like message queues or edge data

  • Highlight, page 1
    The GRE framework modifies the data graph into an Agent-Graph.

  • Highlight, page 1
    The Agent-Graph adds combiner and scatter vertices to the original graph in order to reduce intermachine messaging.

  • Highlight, page 1
    costly

  • Highlight, page 1
    IBM’s X-Pregel [Bao and Suzumura 2013],

  • Highlight, page 1
    plateaus

  • Highlight, page 1
    Computation for the combiner must be commutative and associative because order cannot be guaranteed

  • Underline, page 1
    Conversely

  • Highlight, page 1
    For algorithms that combine vertices into a supervertex, like Boruvka’s Minimum Spanning Tree [Chung and Condon 1996]

  • Highlight, page 1
    counterintuitively

  • Highlight, page 1
    Pregel, including ACM Computing Surveys, Vol. 48, No. 2, Article 25, Publication date: October 2015. Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks 25:17 its open-source implementations [Avery 2011; Seo et al. 2010] and several related variants [Salihoglu and Widom 2013; Bao and Suzumura 2013; Redekopp et al. 2013].

  • Highlight, page 1
    The user provides two functions, one function that executes across each vertex in the active subset and another function that exe- cutes all outgoing edges in the subset.

  • Highlight, page 1
    Edge Centric. The X-Stream framework provides an edge-centric two-phase Scatter- Gather programming model [Roy et al. 2013],

  • Highlight, page 1
    Push Versus Pull. The flow of information for vertex programs can be character- ized as data being pushed or pulled [Nguyen et al. 2013; Hant et al. 2014; Cheng et al. 2012].

  • Highlight, page 1
    Ligra is a single-machine graph-processing framework that dynamically switches between push- and pull-based operators based on a threshold.

  • Highlight, page 1
    interpartition edges

  • Highlight, page 1
    However, for graphs of even medium size, the high computational cost and necessary random access of the entire graph render METIS and related heuristics impractical.

  • Highlight, page 1
    The densification problem is addressed in Vaquero et al. [2014], wherein

  • Highlight, page 1
    More advanced label propagation schemes for partitioning are presented in Wang et al. [2014] and Slota et al. [2014].

  • Highlight, page 1
    GraphBuilder [Jain et al. 2013] is a similar library ACM Computing Surveys, Vol. 48, No. 2, Article 25, Publication date: October 2015. 25:20  R. R. McCune et al. that, in addition to partitioning, supports an extensive variety of graph-loading-related processing tasks.

  • Highlight, page 2
    the partitioner may temporarily store a vertex and decide the partitioning later [Stanton and Kliot 2012];

  • Highlight, page 2
    however, experiments demonstrate that performance remains relatively consistent for breadth-first, depth- first, and random orderings of a graph [Stanton and Kliot 2012; Tsourakakis et al. 2014].

  • Highlight, page 2
    linear deterministic greedy (LDG), a heuristic that assigns a vertex to the parti- tion with which it shares the most edges while weighted by a penalty function linearly associated with a partition’s remaining capacity.

  • Highlight, page 2
    restreaming graph partitioning model, where a streaming partitioner is provided ac- cess to previous stream results [Nishimura and Ugander 2013].

  • Highlight, page 2
    eightfold

  • Highlight, page 2
    thorough analysis

  • Highlight, page 2
    too computationally expensive

  • Highlight, page 2
    Good workload balance for skewed degree distributions can also be achieved with degree-based hashing [Xie et al. 2014].

  • Highlight, page 2
    vary drastically over the course of computation, which creates processing imbalances and increases runtime.

  • Highlight, page 2
    such as graph coarsening [Wang et al. 2014].

  • Highlight, page 2
    According to Salihoglu and Widom [2013], a dynamic repartitioning strategy must directly address (1) how to select vertices to reassign, (2) how and when to move the assigned vertices, and (3) how to locate the reassigned vertices.

  • Highlight, page 2
    the loading and partitioning can be performed in parallel [Salihoglu and Widom 2013].

  • Highlight, page 2
    XPregel [Bao and Suzumura 2013] supports multithreading by dividing a partition into a user-defined number of sub- partitions

  • Highlight, page 2
    When a failure occurs, the system rolls back to the most recently saved point, all partitions are reloaded, and the entire system resumes process- ing from the checkpoint.

  • Highlight, page 2
    GraphLab [Low et al. 2012] implements asynchronous vertex checkpointing, based on Chandy-Lamport [Chandy and Lamport 1985] snapshots,

  • Highlight, page 2
    they are highly scal- able while providing a simple programming interface,

  • Highlight, page 2
    dictated

  • Highlight, page 2
    GraphChi. The seminal single-machine TLAV framework is GraphChi [Kyrola et al. 2012],

  • Highlight, page 2
    PathGraph also implements a path-centric compact storage system that improves compactness and locality [Yuan et al. 2014]. Because most iterative graph algorithms involve path traversal,

  • Highlight, page 2
    retaining

  • Highlight, page 2
    in varying degrees

  • Highlight, page 2
    shared either through vertex programs on boundary nodes or, in the case of Blogel, directly between subgraphs

  • Highlight, page 2
    Collectively, subgraph-centric frameworks dra- matically outperform TLAV frameworks, often by orders of magnitude in terms of computing time, number of messages, and total supersteps [Tian et al. 2013; Yan et al. 2014a].

  • Highlight, page 2
    A vertex subset interface is implemented in Ligra [Shun and Blelloch 2013].

  • Highlight, page 2
    Similarly, the Single Pivot (SP) optimization [Salihoglu and Widom 2014], first pre- sented in Quick et al. [2012], also temporarily adopts a global view.

  • Highlight, page 2
    the Parallel Boost Graph Library [Gregor and Lumsdaine 2005]

  • Highlight, page 2
    first-class citizens

  • Highlight, page 2
    Databases offer local or online queries, such as one-hop neighbors, whereas TLAV systems iteratively process the entire graph offline in batch

  • Highlight, page 3
    Distributed algorithms are a mature field of study [Lynch 1996],

  • Highlight, page 3
    Not all graphs are large enough to necessitate distributed processing, and not all graph problems need the whole graph to be computed iteratively.

© 著作权归作者所有

共有 人打赏支持
wdfnst
粉丝 2
博文 18
码字总数 22859
作品 1
宁波
Graphlab实现分析:图的存储一

前一段时间参与了一个迭代计算平台的开发,对于内存计算和图计算产生了比较浓厚的兴趣,这期间也阅读了spark和pregel的相关论文,了解一下BSP模型,但总觉得看论文太抽象了,于是选择阅读gra...

谈吐鱼 ⋅ 2014/01/21 ⋅ 0

Cocos2dx-OpenGL ES2.0教程:编写自己的shader(2)

在上篇文章中,我给大家介绍了如何在cocos2d-x里面绘制一个三角形,当时我们使用的是cocos2d-x引擎自带的shader和一些辅助函数。在本文中,我将演示一下如何编写自己的shader,同时,我们还会...

乐逍遥jun ⋅ 2016/02/22 ⋅ 0

C++ Exercises(一)

一个3D向量类 // Vertex3D.h: interface for the Vertex3D class. // ////////////////////////////////////////////////////////////////////// class Vertex3D {//3维向量类 private: dou......

嗯哼9925 ⋅ 2017/12/27 ⋅ 0

Direct3D学习(一):3D Sierpinski镂垫绘制

自己几何也太差劲了,时间都花在计算坐标位置上了 图片附件: Sierpinski.JPG (2007-3-29 00:56, 39.68 K) 附件: D3DStudy.exe (2007-3-29 00:56, 64 K) 主要算法,就是个递归: /**// 三角形...

长平狐 ⋅ 2012/11/12 ⋅ 0

js算法: 图的两种表示方法以及广度优先算法

图分为有向图和无向图,图的表示方法有两种,且都可以表示有向图或者无向图: 1. 邻接链表标示 2. 矩阵标示 如下图: 使用邻接链表标示: 使用矩阵标示[北京, 武汉, 上海, 西安, 拉萨]分别为 v1-v...

深山猎人 ⋅ 2016/07/05 ⋅ 0

hive on tez 运行时抛 java.lang.NoClassDefFoundError: com/esotericsoftware/kryo/Serializer

配置hive on tez 完成之后运行sql,直接抛出如下异常,按照文档搭建,不知道什么配置除了问题,求解惑: `Status: Failed Vertex failed, vertexName=Map 1, vertexId=vertex1502854421152000110...

guojinyun ⋅ 2017/08/16 ⋅ 2

cocos2dx(3.X)中使用shader

cocos2dx(3.X)中使用shader 标签: cocos2d-xshader 2016-07-20 12:12 2513人阅读 评论(0) 收藏 举报 分类: OpenGL(10) 版权声明:本文为博主原创文章,未经博主允许不得转载。 目录(?)[+...

panpan123_ ⋅ 2017/11/02 ⋅ 0

OpenGL vertext shader 属性设置

typedef struct _vertex{ GLfloat position[2]; GLfloat colors[4]; } Vertex; //定义顶点 GLfloat positions[NumVertices][2] = { { -0.90, -0.90 }, // Triangle 1 { 0.85, -0.90 }, { -0.......

yizhangxyz ⋅ 2016/06/28 ⋅ 0

shader三种变量类型(uniform,attribute和varying)

uniform变量在vertex和fragment两者之间声明方式完全一样,则它可以在vertex和fragment共享使用。(相当于一个被vertex和fragment shader共享的全局变量) uniform变量一般用来表示:变换矩阵...

扶殊88 ⋅ 2015/09/24 ⋅ 0

apache开源项目 -- tez

为了更高效地运行存在依赖关系的作业(比如Pig和Hive产生的MapReduce作业),减少磁盘和网络IO,Hortonworks开发了DAG计 算框架Tez。Tez是从MapReduce计算框架演化而来的通用DAG计算框架,可...

文艺小青年 ⋅ 2017/06/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python爬虫,抓取淘宝商品评论内容

作为一个资深吃货,网购各种零食是很频繁的,但是能否在浩瀚的商品库中找到合适的东西,就只能参考评论了!今天给大家分享用python做个抓取淘宝商品评论的小爬虫! 思路 我们就拿“德州扒鸡”...

python玩家 ⋅ 20分钟前 ⋅ 0

MySQL 内核深度优化

MYSQL数据库适用场景广泛,相较于Oracle、DB2性价比更高,Web网站、日志系统、数据仓库等场景都有MYSQL用武之地,但是也存在对于事务性支持不太好(MySQL 5.5版本开始默认引擎才是InnoDB事务...

java高级架构牛人 ⋅ 42分钟前 ⋅ 0

用户登录信息-钉子效果(基于jquery2.0)

本js效果使用jquery2.0,清晰的分解用户登录信息的(钉子效果),该效果直接用在作者网站(www.phpkhbd.com)上。 里面的难点有:定时器,延时。 大致效果如下: 一开始: 鼠标放上去的时候:...

宁哥实战课堂 ⋅ 44分钟前 ⋅ 0

解决yum安装报错Protected multilib versions

使用yum安装报错Protected multilib versions原因是因为多个库不能共存,不过更新的话也并不行,但是可以在安装命令后面加上如下一段命令: --setopt=protected_multilib=false 案例: 比如需...

北岩 ⋅ 55分钟前 ⋅ 0

为什么要学习Typescript???

简单来说 目前的typescript就是未来的javascript 为什么?? 这要从ECMA-262标准的第4版说起 对了 我们说的ES5 其实是ECMAScript3.1这个替代性建议被扶正了而已... 那么 第4版标准是什么? 看看...

hang1989 ⋅ 59分钟前 ⋅ 0

linux安装ipfs

一、下载ipfs # cd /usr/local/ipfs/ # wget https://dist.ipfs.io/go-ipfs/v0.4.15/go-ipfs_v0.4.15_linux-amd64.tar.gz # tar -zxvf go-ipfs_v0.4.15_linux-amd64.tar.gz 二、安装ipfs # ......

八戒八戒八戒 ⋅ 今天 ⋅ 0

jvm程序执行慢诊断手册

生产环境最多的几种事故之一就是程序执行慢,如果是web服务的话,表现就是响应时间长。本文分享,从业多年形成的排查守则。 诊断步骤 系统资源查看 首先是系统资源查看,而且必须是在第一步。...

xpbob ⋅ 今天 ⋅ 0

YII2 advanced 高级版本项目搭建-添加API应用以及多应用

一、YII安裝 安裝yii可以用composer安裝,也可以在yii中文社区下载归档文件安装 composer安装就不介绍了,因为要安装composer,比较麻烦,当然安装了composer是最好的,以后安装yii的插件要用...

botkenni ⋅ 今天 ⋅ 0

在jdk1.8的环境下模拟永久代内存溢出

相信不少小伙伴在看深入理解Java虚拟机的时候,作者给我们举例一个demo来发生PermGen space 1、通过List不断添加String.intern(); 2、通过设置对应的-XX:PermSize与-XX:MaxPermSize(更快看到...

虾几把写 ⋅ 今天 ⋅ 0

开发OpenDaylight组件的完整流程

在前面介绍学习了OpenDaylight的几个重要模块后,这里再来介绍下完整开发一个模块的过程。 OSGI的bundles提供被其他OSGI组件调用的服务。这个教程中展示的是Data Packet Service去解析数据包...

wangxuwei ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部