Change search
ReferencesLink to record
Permanent link

Direct link
Boosting Vertex-Cut Partitioning For Streaming Graphs
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
(SICS Swedish ICT)
(SICS Swedish ICT)
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
Show others and affiliations
2016 (English)Conference 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
2016.
Keyword [en]
streaming graph, vertex-cut partitioning, graph partitioning, parallel scalability
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-189864OAI: oai:DiVA.org:kth-189864DiVA: diva2:949508
Conference
5th 2016 IEEE International Congress on Big Data (BigData Congress 2016)
Note

QC 20160923

Available from: 2016-07-20 Created: 2016-07-20 Last updated: 2016-09-23Bibliographically approved

Open Access in DiVA

Boosting Vertex-Cut Partitioning For Streaming Graphs(745 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 745 kBChecksum SHA-512
d254ed07c88daf26e3e779938104410a37f20a26ac609b34d7a4d351d834fb675f97c659b49f8d6a7ead6b769c50e820196352424c7aa57331c64256e02d4538
Type fulltextMimetype application/pdf

Other links

http://www.ieeebigdata.org/2016/cfp.html

Search in DiVA

By author/editor
Peiro Sajjad, HoomanVlassov, Vladimir
By organisation
Software and Computer systems, SCS
Other Electrical Engineering, Electronic Engineering, Information EngineeringComputer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link