Paper Info
Title
Bifennel: Fast Bipartite Graph Partitioning Algorithm For Big Data
Abstract
Graph computing is widely utilized today, which severely requires the ability of processing graphs of billion vertices rapidly for social network analyzing, bio-informational network analyzing and semantic processing. Therefore, graph processing play a significant role in the research and application development. Data of music and movie recommendation and LDA topics can be modeled as bipartite graph and perform the computation with graph processing engines. The most important step before graph computation is graph partitioning. Graph partitioning is a mature technology, however, most of classic graph partitioning algorithms require iterative calculation for several times, which causes high time complexity. Some algorithms with short partitioning time proposed these years, but they cannot be used in bipartite graph directly. This paper proposes a new bipartite graph partitioning algorithm, BiFennel, which effectively decreases graph processing time and network loading by reducing vertex replication factor and maintaining work balance. We implement BiFennel in a popular graph engine called PowerGraph. The performance results show that BiFennel has 29 similar to 55% improvement on communication cost and 21 similar to 49% improvement on overall runtime comparing with Aweto.
Year
DOI
Venue
2015
10.1109/SmartCity.2015.153
2015 IEEE INTERNATIONAL CONFERENCE ON SMART CITY/SOCIALCOM/SUSTAINCOM (SMARTCITY)
Keywords
Field
DocType
Graph processing, Graph partitioning, Bipartite graph, PowerGraph
Strength of a graph,Line graph,Folded cube graph,Computer science,Simplex graph,Algorithm,Theoretical computer science,Null graph,Butterfly graph,Voltage graph,Graph (abstract data type)
Conference
Citations 
PageRank 
References 
0
0.34
10
Authors
5
Name
Order
Citations
PageRank
Lyu-Wei Wang100.34
Shih-Chang Chen200.68
Wenguang Chen3101470.57
Hung-Chang Hsiao425632.34
Yeh-Ching Chung598397.16