An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph
Journal Title: EAI Endorsed Transactions on Collaborative Computing - Year 2015, Vol 1, Issue 5
Abstract
Distributed vertex-centric graph processing systems such as Pregel, Giraph and GPS have acquired significant popularity in recent years. Although the manner in which graph data is partitioned and placed on the computational nodes has considerable impact on the performance of the vertex-centric graph processing cluster, there are very few comprehensive studies on this topic. Towards enhancing our understanding of this important factor, in this paper, we propose a novel model for analyzing the performance of such clusters. Using three graph algorithms as case studies, we also characterize the inherent tradeoff between the computational load distribution and the communication overheads of a BSP cluster. This paper also reports a detailed experimental study investigating the performance of commonly-used graph partitioning mechanisms with respect to their computational load distribution characteristics and the associated communication overheads.
Authors and Affiliations
Amirreza Abdolrashidi, Lakshmish Ramaswamy
Keywords
Related Articles
- EP ID EP45703
- DOI http://dx.doi.org/10.4108/eai.17-12-2015.150810
- Views 305
- Downloads 0
Dynamic State Space Partitioning for Adaptive Simulation Algorithms
Adaptive simulation algorithms can automatically change their configuration during runtime to adapt to changing computational demands of a simulation, e.g., triggered by a changing number of model entities or the executi...
The Richness of Open-ended Play - Rules, feedback and adaptation mechanisms in intelligent play environments
How can we design intelligent play environments for open-ended play that support richness in play? Rich play can be described as ongoing play that changes over time in character, form and nature. This paper elaborates on...
Testing Software Using Swarm Intelligence: A Bee Colony Optimization Approach
Software testing is a critical activity in increasing our confidence of a system under test and improving its quality. The key idea for testing a software application is to minimize the number of faults found in the syst...
A Game Theoretic Approach for Modeling Privacy Settings of an Online Social Network
Users of online social networks often adjust their privacy settings to control how much information on their profiles is accessible to other users of the networks. While a variety of factors have been shown to affect the...
A Scheme for Collaboratively Processing Nearest Neighbor Queries in Oblivious Storage
Security concerns are a substantial impediment to the wider deployment of cloud storage. There are two main concerns on the confidentiality of outsourced data: i) protecting the data, and ii) protecting the access patter...