BiFennel

Fast bipartite graph partitioning algorithm for big data

Lyu Wei Wang, Shih Chang Chen, Wenguang Chen, Hung-Chang Hsiao, Yeh Ching Chung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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~55% improvement on communication cost and 21~49% improvement on overall runtime comparing with Aweto.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages715-720
Number of pages6
ISBN (Electronic)9781509018932
DOIs
Publication statusPublished - 2015
EventIEEE International Conference on Smart City, SmartCity 2015 - Chengdu, China
Duration: 2015 Dec 192015 Dec 21

Other

OtherIEEE International Conference on Smart City, SmartCity 2015
CountryChina
CityChengdu
Period15-12-1915-12-21

Fingerprint

Graph Partitioning
Bipartite Graph
partitioning
Graph in graph theory
Processing
movies
engine
social network
Engines
music
semantics
Engine
cause
communication
ability
costs
Communication Cost
Semantics
performance
time

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Media Technology
  • Computer Science Applications
  • Signal Processing
  • Computer Networks and Communications
  • Modelling and Simulation
  • Sociology and Political Science
  • Urban Studies

Cite this

Wang, L. W., Chen, S. C., Chen, W., Hsiao, H-C., & Chung, Y. C. (2015). BiFennel: Fast bipartite graph partitioning algorithm for big data. In Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015 (pp. 715-720). [7463807] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SmartCity.2015.153
Wang, Lyu Wei ; Chen, Shih Chang ; Chen, Wenguang ; Hsiao, Hung-Chang ; Chung, Yeh Ching. / BiFennel : Fast bipartite graph partitioning algorithm for big data. Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 715-720
@inproceedings{d9f398153b9b415ca07dde7521983155,
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~55{\%} improvement on communication cost and 21~49{\%} improvement on overall runtime comparing with Aweto.",
author = "Wang, {Lyu Wei} and Chen, {Shih Chang} and Wenguang Chen and Hung-Chang Hsiao and Chung, {Yeh Ching}",
year = "2015",
doi = "10.1109/SmartCity.2015.153",
language = "English",
pages = "715--720",
booktitle = "Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

Wang, LW, Chen, SC, Chen, W, Hsiao, H-C & Chung, YC 2015, BiFennel: Fast bipartite graph partitioning algorithm for big data. in Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015., 7463807, Institute of Electrical and Electronics Engineers Inc., pp. 715-720, IEEE International Conference on Smart City, SmartCity 2015, Chengdu, China, 15-12-19. https://doi.org/10.1109/SmartCity.2015.153

BiFennel : Fast bipartite graph partitioning algorithm for big data. / Wang, Lyu Wei; Chen, Shih Chang; Chen, Wenguang; Hsiao, Hung-Chang; Chung, Yeh Ching.

Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 715-720 7463807.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - BiFennel

T2 - Fast bipartite graph partitioning algorithm for big data

AU - Wang, Lyu Wei

AU - Chen, Shih Chang

AU - Chen, Wenguang

AU - Hsiao, Hung-Chang

AU - Chung, Yeh Ching

PY - 2015

Y1 - 2015

N2 - 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~55% improvement on communication cost and 21~49% improvement on overall runtime comparing with Aweto.

AB - 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~55% improvement on communication cost and 21~49% improvement on overall runtime comparing with Aweto.

UR - http://www.scopus.com/inward/record.url?scp=84973863284&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973863284&partnerID=8YFLogxK

U2 - 10.1109/SmartCity.2015.153

DO - 10.1109/SmartCity.2015.153

M3 - Conference contribution

SP - 715

EP - 720

BT - Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Wang LW, Chen SC, Chen W, Hsiao H-C, Chung YC. BiFennel: Fast bipartite graph partitioning algorithm for big data. In Proceedings - 2015 IEEE International Conference on Smart City, SmartCity 2015, Held Jointly with 8th IEEE International Conference on Social Computing and Networking, SocialCom 2015, 5th IEEE International Conference on Sustainable Computing and Communications, SustainCom 2015, 2015 International Conference on Big Data Intelligence and Computing, DataCom 2015, 5th International Symposium on Cloud and Service Computing, SC2 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 715-720. 7463807 https://doi.org/10.1109/SmartCity.2015.153