Artikel in Tagungsband INPROC-2018-45

Bibliograph.
Daten
Mayer, Christian; Mayer, Ruben; Bhowmik, Sukanya; Epple, Lukas; Rothermel, Kurt: HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion.
In: Proceedings of the 2018 IEEE International Conference on Big Data (BigData '18); Seattle, WA, USA, December 10-13, 2018.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik.
S. 1-10, englisch.
IEEE, Dezember 2018.
Artikel in Tagungsband (Konferenz-Beitrag).
CR-Klassif.C.2.4 (Distributed Systems)
Kurzfassung

Many important real-world applications---such as social networks or distributed data bases---can be modeled as hypergraphs. In such a model, vertices represent entities---such as users or data records---whereas hyperedges model a group membership of the vertices---such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hypergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to the state of the art.

Volltext und
andere Links
PDF (1637111 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
Eingabedatum9. November 2018
   Publ. Institut   Publ. Informatik