Title | ||
---|---|---|
Enabling application-aware flexible graph partition mechanism for parallel graph processing systems. |
Abstract | ||
---|---|---|
With the emerging of the large-scale graph data, Pregel-like graph parallel processing systems have been an essential tool to efficiently process the graph data. The first step to use the Pregel-like systems is to partition the graph into multiple blocks and distribute them on multiple machines. The partition strategy plays a significant role in determining the performance because a good partition could both ensure load balance and optimize network communication overhead, and vice versa. However, existing partition strategies fail to meet the requirements because they suffer from the following drawbacks: (1) they ignore the application features and (2) they ignore the multi-application feature in productive environment. To overcome those drawbacks, we proposed the superblock partition strategy, which utilizes the atomic blocks generated by pre-processing of the original graph and could be constructed and re-constructed dynamically according to the submitted applications in real time. The hash-based and clustering-based pre-partition methods are covered in details. The application feature extraction method and heuristic superblock partition algorithm are proposed to construct the superblocks. Experimental results show that the superblock partition strategy could boost the graph processing performance and its partition efficiency also outperforms the hash-based and topology optimal partition strategy. Copyright (C) 2016 John Wiley & Sons, Ltd. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1002/cpe.3849 | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE |
Keywords | Field | DocType |
parallel graph processing,graph partition,application aware,fast and flexible | Strength of a graph,Computer science,Theoretical computer science,Distance-hereditary graph,Null graph,Clique-width,Graph partition,Voltage graph,Graph (abstract data type),Distributed computing,Complement graph | Journal |
Volume | Issue | ISSN |
29 | SP6 | 1532-0626 |
Citations | PageRank | References |
3 | 0.38 | 19 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fang Dong | 1 | 202 | 35.44 |
Junxue Zhang | 2 | 19 | 3.37 |
Junzhou Luo | 3 | 1257 | 153.97 |
Dian Shen | 4 | 10 | 5.22 |
Jin Jiahui | 5 | 88 | 16.84 |