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.
2015
24th ACM International Conference on Information and Knowledge Management, CIKM 2015
Distributed graph-computing frameworks; Graph partitioning; Load balancing; Replication; Streaming algorithms; Business, Management and Accounting (all); Decision Sciences (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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].
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/863114
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 105
  • ???jsp.display-item.citation.isi??? ND
social impact