Article in Proceedings INPROC-2018-45

BibliographyMayer, 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.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 1-10, english.
IEEE, December 2018.
Article in Proceedings (Conference Paper).
CR-SchemaC.2.4 (Distributed Systems)
Abstract

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.

Full text and
other links
PDF (1637111 Bytes)
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Entry dateNovember 9, 2018
   Publ. Department   Publ. Institute   Publ. Computer Science