BiFennel: Fast bipartite graph partitioning algorithm for big data

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

研究成果: Conference contribution

摘要

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.

原文English
主出版物標題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
編輯Xingang Liu, Peicheng Wang, Yufeng Wang, Mianxiong Dong, Robert C. H. Hsu, Feng Xia, Yuhui Deng
發行者Institute of Electrical and Electronics Engineers Inc.
頁面715-720
頁數6
ISBN(電子)9781509018932
DOIs
出版狀態Published - 2015 一月 1
事件IEEE International Conference on Smart City, SmartCity 2015 - Chengdu, China
持續時間: 2015 十二月 192015 十二月 21

出版系列

名字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

Other

OtherIEEE International Conference on Smart City, SmartCity 2015
國家China
城市Chengdu
期間15-12-1915-12-21

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

指紋 深入研究「BiFennel: Fast bipartite graph partitioning algorithm for big data」主題。共同形成了獨特的指紋。

  • 引用此

    Wang, L. W., Chen, S. C., Chen, W., Hsiao, H. C., & Chung, Y. C. (2015). BiFennel: Fast bipartite graph partitioning algorithm for big data. 於 X. Liu, P. Wang, Y. Wang, M. Dong, R. C. H. Hsu, F. Xia, & Y. Deng (編輯), 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 (頁 715-720). [7463807] (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.. https://doi.org/10.1109/SmartCity.2015.153