Partitioning billionscale hypergraphs

Abstract

In this thesis, we present a hypergraph partitioning algorithm that achieves both, fast partitioning with high locality. The idea is simple but effective: the algorithm grows k disjoint subgraphs based on the neighbourhood relation and the degree distribution in the hypergraph. We performed extensive experiments and showed that our algorithm leads to perfectly balanced partitions with improved locality compared to state-of-the-art, while matching the fast runtime of streaming hypergraph partitioners.

Aufgrund wachsender Kommunikationsnetzwerke und der immer größer werdenden Datenmengen in sozialen Netzwerken hat sich die Nachfrage nach Graph-Verarbeitungs-Systemen deutlich erhöht. Fast alle modernen Kommunikationsnetzwerke, wie z.B. Whatsapp, Facebook oder Reddit bieten heutzutage Gruppenfunktionalitäten an, welche sich sehr einfach mit Hilfe von Hypergraphen modellieren lassen. Um diese großen Hypergraphen verarbeiten zu können, müssen diese durch Hypergraph-Partitionierung auf viele verschiedene Maschinen verteilt werden. Solche Partitionierungs-Algorithmen existieren bereits, bieten jedoch entweder eine schnelle Laufzeit und schlechte Ergebnisse oder gute Ergebnisse und eine schlechte Laufzeit. In dieser Arbeit wird ein neuartiger Partitionierungs-Algorithmus vorgestellt, welcher beides bietet, eine schnelle Laufzeit und gute Ergebnisse. Die dem Algorithmus zugrunde liegende Idee ist einfach aber effektiv: der Algorithmus baut k disjunkte Subgraphen anhand der Nachbarschafts-Information der einzelnen Knoten. Es wurden ausführliche Tests durchgeführt, die zeigen, dass die Ergebnisse dieses Algorithmus eine deutlich verbesserte Lokalität aufweisen im Vergleich zu bereits existierenden Algorithmen, wobei er dennoch eine bessere Laufzeit als diese aufweisen kann.