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

Direktlänk
Referera
Referensformat
  • apa
  • 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
Streaming Graph Partitioning: An Experimental Study
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Programvaruteknik och datorsystem, SCS.ORCID-id: 0000-0001-6171-9586
Systems Group, ETH, Zurich, Switzerland.
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Programvaruteknik och datorsystem, SCS.
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Programvaruteknik och datorsystem, SCS.ORCID-id: 0000-0002-6779-7435
2018 (Engelska)Ingår i: Proceedings of the VLDB Endowment, E-ISSN 2150-8097, Vol. 11, nr 11, s. 1590-1603Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Graph partitioning is an essential yet challenging task for massive graph analysis in distributed computing. Common graph partitioning methods scan the complete graph to obtain structural characteristics offline, before partitioning. However, the emerging need for low-latency, continuous graph analysis led to the development of online partitioning methods. Online methods ingest edges or vertices as a stream, making partitioning decisions on the fly based on partial knowledge of the graph. Prior studies have compared offline graph partitioning techniques across different systems. Yet, little effort has been put into investigating the characteristics of online graph partitioning strategies.

In this work, we describe and categorize online graph partitioning techniques based on their assumptions, objectives and costs. Furthermore, we employ an experimental comparison across different applications and datasets, using a unified distributed runtime based on Apache Flink. Our experimental results showcase that model-dependent online partitioning techniques such as low-cut algorithms offer better performance for communication-intensive applications such as bulk synchronous iterative algorithms, albeit higher partitioning costs. Otherwise, model-agnostic techniques trade off data locality for lower partitioning costs and balanced workloads which is beneficial when executing data-parallel single-pass graph algorithms.

Ort, förlag, år, upplaga, sidor
ACM Digital Library, 2018. Vol. 11, nr 11, s. 1590-1603
Nyckelord [en]
graph partitioning, streaming graph processing, stream processing
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datalogi
Identifikatorer
URN: urn:nbn:se:kth:diva-236053DOI: 10.14778/3236187.3236208ISI: 000452537300022Scopus ID: 2-s2.0-85058876764OAI: oai:DiVA.org:kth-236053DiVA, id: diva2:1255661
Anmärkning

QC 20181015

Tillgänglig från: 2018-10-14 Skapad: 2018-10-14 Senast uppdaterad: 2024-03-15Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Abbas, ZainabCarbone, ParisVlassov, Vladimir

Sök vidare i DiVA

Av författaren/redaktören
Abbas, ZainabCarbone, ParisVlassov, Vladimir
Av organisationen
Programvaruteknik och datorsystem, SCS
I samma tidskrift
Proceedings of the VLDB Endowment
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • 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