Dynamic Block Reassignment for Load Balancing of Block Centric Graph Processing Systems

KIPS Transactions on Software and Data Engineering, Vol. 7, No.5, pp.177-188, May 2018
10.3745/KTSDE.2018.7.5.177, Full Text

Abstract

The scale of graph data has been increased rapidly because of the growth of mobile Internet applications and the proliferation of social network services. This brings upon the imminent necessity of efficient distributed and parallel graph processing approach since the size of these large-scale graphs are easily over a capacity of a single machine. Currently, there are two popular parallel graph processing approaches, vertex-centric graph processing and block centric processing. While a vertex-centric graph processing approach can easily be applied to the parallel processing system, a block-centric graph processing approach is proposed to compensate the drawbacks of the vertex-centric approach. In these systems, the initial quality of graph partition affects to the overall performance significantly. However, it is a very difficult problem to divide the graph into optimal states at the initial phase. Thus, several dynamic load balancing techniques have been studied that suggest the progressive partitioning during the graph processing time. In this paper, we present a load balancing algorithms for the block-centric graph processing approach where most of dynamic load balancing techniques are focused on vertex-centric systems. Our proposed algorithm focus on an improvement of the graph partition quality by dynamically reassigning blocks in runtime, and suggests block split strategy for escaping local optimum solution.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from October 15, 2016)

Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


Cite this paper

[KIPS Transactions Style]
Y. Kim, M. Bae, and S. Oh, "Dynamic Block Reassignment for Load Balancing of Block Centric Graph Processing Systems," KIPS Transactions on Software and Data Engineering, Vol.7, No.5, pp.177-188, 2018, DOI: 10.3745/KTSDE.2018.7.5.177.

[IEEE Style]
Yewon Kim, Minho Bae, and Sangyoon Oh, "Dynamic Block Reassignment for Load Balancing of Block Centric Graph Processing Systems," KIPS Transactions on Software and Data Engineering, vol. 7, no. 5, pp. 177-188, 2018. DOI: 10.3745/KTSDE.2018.7.5.177.

[ACM Style]
Kim, Y., Bae, M., and Oh, S. 2018. Dynamic Block Reassignment for Load Balancing of Block Centric Graph Processing Systems. KIPS Transactions on Software and Data Engineering, 7, 5, (2018), 177-188. DOI: 10.3745/KTSDE.2018.7.5.177.