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 hy-pergraph 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 streaming partitioning.
%0 Conference Paper
%1 8621968
%A Mayer, Christian
%A Mayer, Ruben
%A Bhowmik, Sukanya
%A Epple, Lukas
%A Rothermel, Kurt
%B 2018 IEEE International Conference on Big Data (Big Data)
%D 2018
%K myown
%P 458-467
%R 10.1109/BigData.2018.8621968
%T HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion
%X 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 hy-pergraph 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 streaming partitioning.
@inproceedings{8621968,
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 hy-pergraph 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 streaming partitioning.},
added-at = {2023-02-02T16:43:13.000+0000},
author = {Mayer, Christian and Mayer, Ruben and Bhowmik, Sukanya and Epple, Lukas and Rothermel, Kurt},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/2a16f96fc8d208b3082a5881d281677c7/lepple},
booktitle = {2018 IEEE International Conference on Big Data (Big Data)},
doi = {10.1109/BigData.2018.8621968},
interhash = {870103c849a448956f606c8eb18df0c0},
intrahash = {a16f96fc8d208b3082a5881d281677c7},
keywords = {myown},
month = dec,
pages = {458-467},
timestamp = {2023-02-02T15:51:45.000+0000},
title = {HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion},
year = 2018
}
