PAGE: A Partition Aware Engine for Parallel Graph Computation
Authors:
- 29 May 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 27 (2) , 518-530
Abstract
Graph partition quality affects the overall performance of parallel graph computation systems. The quality of a graph partition is measured by the balance factor and edge cut ratio. A balanced graph partition with small edge cut ratio is generally preferred since it reduces the expensive network communication cost. However, according to an empirical study on Giraph, the performance over well partitioned graph might be even two times worse than simple random partitions. This is because these systems only optimize for the simple partition strategies and cannot efficiently handle the increasing workload of local message processing when a high quality graph partition is used. In this paper, we propose a novel partition aware graph computation engine named PAGE, which equips a new message processor and a dynamic concurrency control model. The new message processor concurrently processes local and remote messages in a unified way. The dynamic model adaptively adjusts the concurrency of the processor based on the online statistics. The experimental evaluation demonstrates the superiority of PAGE over the graph partitions with various qualities.Keywords
Funding Information
- National Natural Science Foundation of China (61272155)
- National Basic Research Program of China (2014CB340405)
This publication has 25 references indexed in Scilit:
- FENNEL2014
- Mizan2013
- Streaming graph partitioning for large distributed graphs2012
- Fast PGAS Implementation of Distributed Graph Algorithms2010
- PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations2009
- Statistical properties of community structure in large social and information networks2008
- Parallel multilevel graph partitioning2002
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Multilevel Algorithms for Multi-Constraint Graph Partitioning1998
- Communicating Sequential Processes1978