Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.
HDRF: Stream-based partitioning for power-law graphs / Petroni, Fabio; Querzoni, Leonardo; Daudjee, Khuzaima; Kamali, Shahin; Iacoboni, Giorgio. - STAMPA. - (2015), pp. 243-252. (Intervento presentato al convegno 24th ACM International Conference on Information and Knowledge Management, CIKM 2015 tenutosi a Melbourne; Australia) [10.1145/2806416.2806424].
HDRF: Stream-based partitioning for power-law graphs
PETRONI, FABIO;QUERZONI, Leonardo;
2015
Abstract
Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.File | Dimensione | Formato | |
---|---|---|---|
Petroni_HDRF_2015.pdf
solo gestori archivio
Note: https://dl.acm.org/doi/10.1145/2806416.2806424
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.42 MB
Formato
Adobe PDF
|
1.42 MB | Adobe PDF | Contatta l'autore |
Petroni_HDRF_Frontespizio-indice_2015.pdf
accesso aperto
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
3.52 MB
Formato
Adobe PDF
|
3.52 MB | Adobe PDF | |
Petroni_postprint_HDRF_2015.pdf
accesso aperto
Note: https://dl.acm.org/doi/10.1145/2806416.2806424
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.15 MB
Formato
Adobe PDF
|
1.15 MB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.