2013 · 77 citations · 23 references
ComputingCloud ComputingComputer ScienceCloud InfrastructureParallel AlgorithmsParallel ComputingCompute Resource ManagementGraph AnalyticsWorkload PlacementWorkload SchedulingCloud Resource PartitioningGraph ProcessingGraph Processing SystemsGraph Traversal AlgorithmsParallel Graph AlgorithmsWorkload
Graph partitioning is a key issue in graph database processing systems for achieving high efficiency on Cloud. However, the balanced graph partitioning itself is difficult because it is known to be NP-complete. In addition a static graph partitioning cannot keep all graph algorithms efficient for a long time in parallel on Cloud because the workload balancing in different iterations for different graph algorithms are all possible different. In this paper, we investigate graph behaviors by exploring the working window (we call it wind) changes, where a working window is a set of active vertices that a graph algorithm really needs to access in parallel computing. We investigated nine classic graph algorithms using real datasets, and propose simple yet effective policies that can achieve both high graph workload balancing and efficient partition on Cloud.
23
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
A bridging model for parallel computation
Leslie G. Valiant · Communications of the ACM · 1990 · 3.7K citations · Full text