Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.
翻译:将一个(超级)图的顶端分割成一个大致平衡的区块, 使区块之间运行的( 超级) 很少( 超级) 的顶部成为大型分布式处理的关键问题。 目前使用低计算资源分割巨型( 高) 的倾向是流算法。 在这项工作中, 我们提议 Freight: 快速 strreamInG 高射速测算法, 这是对广受欢迎的基于图形的算法 Fenneel 的调整。 通过使用高效的数据结构, 我们使FREight的总体运行线性地依赖于高射线和内存消耗的直线性取决于网和区的数目。 我们广泛实验的结果展示了FREight作为流高射速隔断的高效和有效解决方案的前景。 我们的算法展示了与Hashing算法的竞争运行时间, 在四分之三的事例中观察到了四个最大系数的差别。 重要的是, 我们的发现显示FREight相对于所有现有( 缓冲) 流算法和内存消耗量消耗量消耗量的线的线上取决于网和区块的数目。 我们的大规模移动算算算法 显示, 向具有前景的系统的高度分析工具的高度分析 向上显示, 向有希望的高度分析工具的高度分析法 。