Paper Info
Title
Towards Systematic Parallelization of Graph Transformations Over Pregel.
Abstract
Graphs can be used to model many kinds of data, from traditional datasets to social networks or semi-structured datasets. To process large graphs, many systems have been proposed. The Pregel programming model is popular, thanks to its scalability. Although Pregel is simple to understand and use, it is of low-level in programming and requires developers to write programs that are hard to maintain and need to be carefully optimized. On the other hand, structural recursion is powerful to systematically construct efficient parallel programs on lists, arrays and trees, but it has not yet been applied to graphs. In this paper, we propose an efficient method for parallel evaluation of structural recursion on graphs, which is suitable for Pregel. We design and implement a high-level parallel programming framework where a domain-specific language (DSL) is provided to ease the programing task. Specifications written in the DSL are automatically compiled into Pregel programs that are scalable for large graphs. Experimental results show that our framework outperforms the original evaluation of structural recursion, and achieves good scalability and speedup for real datasets.
Year
DOI
Venue
2017
10.1007/s10766-016-0418-5
International Journal of Parallel Programming
Keywords
Field
DocType
Structural recursion, Graph transformation, Parallel programming, Pregel programming model
Graph,Social network,Programming paradigm,Computer science,Digital subscriber line,Parallel computing,Theoretical computer science,Graph rewriting,Recursion,Speedup,Scalability
Journal
Volume
Issue
ISSN
45
2
1573-7640
Citations 
PageRank 
References 
2
0.38
16
Authors
2
Name
Order
Citations
PageRank
Le-Duc Tung1141.98
Zhenjiang Hu2134199.25