Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Boosting vertex-cut partitioning for streaming graphs
RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
KTH Royal Institute of Technology, Sweden.
Show others and affiliations
2016 (English)In: Proceedings - 2016 IEEE International Congress on Big Data, BigData Congress 2016, Institute of Electrical and Electronics Engineers Inc. , 2016, p. 1-8Conference paper, Published paper (Refereed)
Abstract [en]

While the algorithms for streaming graph partitioning are proved promising, they fall short of creating timely partitions when applied on large graphs. For example, it takes 415 seconds for a state-of-the-art partitioner to work on a social network graph with 117 millions edges. We introduce an efficient platform for boosting streaming graph partitioning algorithms. Our solution, called HoVerCut, is Horizontally and Vertically scalable. That is, it can run as a multi-threaded process on a single machine, or as a distributed partitioner across multiple machines. Our evaluations, on both real-world and synthetic graphs, show that HoVerCut speeds up the process significantly without degrading the quality of partitioning. For example, HoVerCut partitions the aforementioned social network graph with 117 millions edges in 11 seconds that is about 37 times faster.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc. , 2016. p. 1-8
Keywords [en]
Graph partitioning, Parallel scalability, Streaming graph, Vertex-cut partitioning, Big data, Graph partitioning algorithms, Multiple machine, Single- machines, State of the art, Synthetic graphs, Vertex-cut, Graph theory
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:ri:diva-43934DOI: 10.1109/BigDataCongress.2016.10Scopus ID: 2-s2.0-84994558691ISBN: 9781509026227 (print)OAI: oai:DiVA.org:ri-43934DiVA, id: diva2:1392950
Conference
5th IEEE International Congress on Big Data, BigData Congress 2016, 27 June 2016 through 2 July 2016
Available from: 2020-02-14 Created: 2020-02-14 Last updated: 2020-02-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus
By organisation
SICS
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 18 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf