Paper Info
Title
Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing
Abstract
The vertex-centric programming model is an established computational paradigm recently incorporated into distributed processing frameworks to address challenges in large-scale graph processing. Billion-node graphs that exceed the memory capacity of commodity machines are not well supported by popular Big Data tools like MapReduce, which are notoriously poor performing for iterative graph algorithms such as PageRank. In response, a new type of framework challenges one to “think like a vertex” (TLAV) and implements user-defined programs from the perspective of a vertex rather than a graph. Such an approach improves locality, demonstrates linear scalability, and provides a natural way to express and compute many iterative graph algorithms. These frameworks are simple to program and widely applicable but, like an operating system, are composed of several intricate, interdependent components, of which a thorough understanding is necessary in order to elicit top performance at scale. To this end, the first comprehensive survey of TLAV frameworks is presented. In this survey, the vertex-centric approach to graph processing is overviewed, TLAV frameworks are deconstructed into four main components and respectively analyzed, and TLAV implementations are reviewed and categorized.
Year
DOI
Venue
2015
10.1145/2818185
ACM Computing Surveys
Keywords
Field
DocType
Design,Algorithms,Graph processing,pregel,distributed systems,Big Data,distributed algorithms
Graph database,Programming paradigm,Computer science,Theoretical computer science,Distributed algorithm,Graph rewriting,Wait-for graph,Graph (abstract data type),Feedback vertex set,Distributed computing,Scalability
Journal
Volume
Issue
ISSN
48
2
0360-0300
Citations 
PageRank 
References 
86
2.11
133
Authors
3
Search Limit
100133
Name
Order
Citations
PageRank
Robert Ryan McCune1862.11
Tim Weninger257646.14
Greg Madey31539.65