Abstract | ||
---|---|---|
A significant part of the data produced every day by online services is structured as a graph. Therefore, there is the need for efficient processing and analysis solutions for large scale graphs. Among the others, the balanced graph partitioning is a well known NP-complete problem with a wide range of applications. Several solutions have been proposed so far, however most of the existing state-of-the-art algorithms are not directly applicable in very large-scale distributed scenarios. A recently proposed promising alternative exploits a vertex-center heuristics to solve the balance graph partitioning problem. Their algorithm is massively parallel: there is no central coordination, and each node is processed independently. Unfortunately, we found such algorithm to be not directly exploitable in current BSP-like distributed programming frameworks. In this paper we present the adaptations we applied to the original algorithm while implementing it on Spark, a state-of-the-art distributed framework for data processing. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-319-14325-5_12 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
graph partitioning,distributed algorithm,approximated algorithm | Spark (mathematics),Massively parallel,Computer science,Parallel computing,Theoretical computer science,Distributed algorithm,Graph bandwidth,Graph partition,Graph (abstract data type),Reverse-delete algorithm,Moral graph,Distributed computing | Conference |
Volume | ISSN | Citations |
8805 | 0302-9743 | 13 |
PageRank | References | Authors |
0.68 | 18 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Emanuele Carlini | 1 | 166 | 20.15 |
Patrizio Dazzi | 2 | 249 | 24.78 |
Andrea Esposito | 3 | 13 | 0.68 |
Alessandro Lulli | 4 | 82 | 10.35 |
Laura Ricci | 5 | 151 | 14.12 |