Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Distributed Algorithm for Large-Scale Graph Partitioning
KTH, Skolan för informations- och kommunikationsteknik (ICT), Programvaruteknik och Datorsystem, SCS. Computer System Lab. (CSL), SICS Swedish, Sweden.
Computer System Lab. (CSL), SICS Swedish, Sweden.
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsnät.ORCID-id: 0000-0003-4516-7317
MTA SZTE Research Group on AI, Hungarian Academy of Sciences and University of Szeged, Hungary.
Visa övriga samt affilieringar
2015 (Engelska)Ingår i: ACM Transactions on Autonomous and Adaptive Systems, ISSN 1556-4665, E-ISSN 1556-4703, Vol. 10, nr 2, artikel-id 12Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Balanced graph partitioning is an NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems, including the optimal storage of large sets of graph-structured data over several hosts. However, in very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable because they typically involve frequent global operations over the entire graph. In this article, we propose a fully distributed algorithm called JA-BE-JA that uses local search and simulated annealing techniques for two types of graph partitioning: edge-cut partitioning and vertex-cut partitioning. The algorithm is massively parallel: There is no central coordination, each vertex is processed independently, and only the direct neighbors of a vertex and a small subset of random vertices in the graph need to be known locally. Strict synchronization is not required. These features allow JA-BE-JA to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We show that the minimal edge-cut value empirically achieved by JA-BE-JA is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks, JA-BE-JA outperforms Metis. We also show that JA-BE-JA computes very low vertex-cuts, which are proved significantly more effective than edge-cuts for processing most real-world graphs.

Ort, förlag, år, upplaga, sidor
ACM, 2015. Vol. 10, nr 2, artikel-id 12
Nationell ämneskategori
Teknik och teknologier
Forskningsämne
Datalogi
Identifikatorer
URN: urn:nbn:se:kth:diva-170128DOI: 10.1145/2714568ISI: 000356389900006Scopus ID: 2-s2.0-84930973235OAI: oai:DiVA.org:kth-170128DiVA, id: diva2:827364
Projekt
End to End Clouds
Forskningsfinansiär
Stiftelsen för strategisk forskning (SSF)
Anmärkning

QC 20150629

Tillgänglig från: 2015-06-26 Skapad: 2015-06-26 Senast uppdaterad: 2019-10-02Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Haridi, Seif

Sök vidare i DiVA

Av författaren/redaktören
Rahimian, FatemehPayberah, Amir H.Girdzijauskas, SarunasHaridi, Seif
Av organisationen
Programvaruteknik och Datorsystem, SCSKommunikationsnät
I samma tidskrift
ACM Transactions on Autonomous and Adaptive Systems
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 90 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf