HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion
HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion
复制标题
HYPE：具有邻域扩展的大规模超图分区
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
K. Rothermel
中科院分区：
文献类型：
--
作者：
C. Mayer;R. Mayer;Sukanya Bhowmik;Lukas Epple;K. Rothermel
许多重要的现实世界的应用程序，如社交网络或分布式数据库，可以建模为超图。在这样的模型中，顶点代表实体（比如用户或数据记录），而超边则对顶点的组成员关系（比如特定主题的作者身份或特定复制分片中数据记录的成员关系）进行建模。为了优化这样的应用，我们需要一个高效和有效的解决方案，NP-硬平衡k路超图划分问题。然而，现有的超图划分器，规模非常大的图不有效地利用超图结构时，执行分区决策。我们提出了HYPE，超图partitionier，利用超图中的顶点之间的邻域关系，使用一个有效的实现邻域扩展。与流式分区相比，HYPE将分区质量提高了95%，并将运行时间减少了39%。
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.