Boosting vertex-cut partitioning for streaming graphsShow 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
2020-02-142020-02-142020-02-19Bibliographically approved