Hypergraph Partitioning for Big Data Applications
Wenyin Yang, Li Ma, Ruchun Cui, Guojun Wang · 2018
Scalability is an important issue for big data management, and minimizing the query cost among multi-hosts in the Cloud is benefit to horizontal scaling. Hypergraph provides a good tool to model data and data relationships of complex networks, the typical big data applications. and partitioning a hypergraph helps to partition the query loads on several hosts. Since balanced hypergraph partitioning is an NP-hard problem, a few heuristic net-cut hypergraph partitioning algorithms have been developed. However, vertex-cut hypergraph partitioning methods would be effective than net-cut hypergraph partitioning ones. In this paper, we proposed a heuristic vertex-cut hypergraph partitioning algorithm, namely vcFM, which partition the hypergraph into balanced sub-hypergraph as required, based on the move of hyperedge. We show the feasibility of this idea, evaluate our method on the Facebook dataset with a variety of settings, and compare it against two alternative solutions. Experiment findings show that vcFM is scalable and outperforms the other two partitioners on low cutsize while retaining balanced partitions.