Author : Prashant Patne 1
Date of Publication :7th April 2016
Abstract: Graph partition quality affects the whole working of parallel graph computation systems. The quality of a graph partition is calculated by the equity factor and edge cut ratio. A balanced graph partition with small edge cut ratio is generally preferred since it reduces the costly network conversation cost. However, according to an empirical study on Graph, the achievement over well partitioned graph might be even two times worse than simple random partitions. This is because these systems only enhance for the easy partition strategies and cannot efficiently handle the increasing workload of local message transmission when a high quality graph partition is used. In this paper, we propose a novel partition aware graph estimation engine named PAGE, which qualify a new message processor and a dynamic concurrency control model. The new message processor simultaneously processes local and remote messages in a unified way. The dynamic model adaptively adjusts the compatibility of the processor based on the online statistics. The experimental evaluation demonstrates the prestige of PAGE over the graph partitions with various qualities.
Reference :
-
- Parallel multilevel graph partitioning, conference paper MAY 1996
- N. Backman, R. Fonseca, and U. C¸ etintemel, “Managing parallel- ism for stream processing in the cloud,” in Proc. 1st Int. Workshop Hot Topics Cloud Data Process., 2012
- P. Boldi and S. Vigna, “The webgraph framework I: Compression techniques,” in Proc. 13th Int. Conf. World Wide Web, 2004.