Heterogeneous environment aware streaming graph partitioning

Xu, Ning, Cui, Bin, Chen, Lei, Huang, Zi and Shao, Yingxia (2015) Heterogeneous environment aware streaming graph partitioning. IEEE Transactions On Knowledge and Data Engineering, 27 6: 1560-1572. doi:10.1109/TKDE.2014.2377743

Author Xu, Ning
Cui, Bin
Chen, Lei
Huang, Zi
Shao, Yingxia
Title Heterogeneous environment aware streaming graph partitioning
Journal name IEEE Transactions On Knowledge and Data Engineering   Check publisher's open access policy
ISSN 1041-4347
Publication date 2015-06-01
Year available 2015
Sub-type Article (original research)
DOI 10.1109/TKDE.2014.2377743
Open Access Status Not yet assessed
Volume 27
Issue 6
Start page 1560
End page 1572
Total pages 13
Place of publication Piscataway, NJ United States
Publisher Institute of Electrical and Electronics Engineers
Language eng
Abstract With the increasing availability of graph data and widely adopted cloud computing paradigm, graph partitioning has become an efficient pre-processing technique to balance the computing workload and cope with the large scale of input data. Since the cost of partitioning the entire graph is strictly prohibitive, there are some recent tentative works towards streaming graph partitioning which run faster, are easily parallelized, and can be incrementally updated. Most of the existing works on streaming partitioning assume that worker nodes within a cluster are homogeneous in nature. Unfortunately, this assumption does not always hold. Experiments show that these homogeneous algorithms suffer a significant performance degradation when running at heterogeneous environment. In this paper, we propose a novel adaptive streaming graph partitioning approach to cope with heterogeneous environment. We first formally model the heterogeneous computing environment with the consideration of the unbalance of computing ability (e.g., the CPU frequency) and communication ability (e.g., the network bandwidth) for each node. Based on this model, we propose a new graph partitioning objective function that aims to minimize the total execution time of the graph-processing job. We then explore some simple yet effective streaming algorithms for this objective function that can achieve balanced and efficient partitioning result. Extensive experiments are conducted on a moderate sized computing cluster with real-world web and social network graphs. The results demonstrate that the proposed approach achieves significant improvement compared with the state-of-the-art solutions.
Keyword BSP Model
Graph partitioning
Heterogeneous environment
Streaming algorithms
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2016 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 10 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 24 May 2015, 10:15:32 EST by System User on behalf of School of Information Technol and Elec Engineering