Summary of Large-Scale Grapb Partitioning Algoritbms

Jinfeng Xu; Yihong Dong; Shiyi Wang; Xianmang He; Huahui Chen

doi:10.3969/j.issn.1000-0801.2014.07.016

您当前的位置：

首页 >

文章列表页 >

Summary of Large-Scale Grapb Partitioning Algoritbms

summarize | 更新时间：2024-06-05

- Summary of Large-Scale Grapb Partitioning Algoritbms
- Telecommunications Science Vol. 30, Issue 7, Pages: 100-106(2014)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.1000-0801.2014.07.016
  CLC：
- Published Online：2014-07，
  
  Published：20 July 2014
- 稿件说明：
移动端阅览
Jinfeng Xu, Yihong Dong, Shiyi Wang, et al. Summary of Large-Scale Grapb Partitioning Algoritbms[J]. Telecommunications science, 2014, 30(7): 100-106.
DOI：

Jinfeng Xu, Yihong Dong, Shiyi Wang, et al. Summary of Large-Scale Grapb Partitioning Algoritbms[J]. Telecommunications science, 2014, 30(7): 100-106. DOI： 10.3969/j.issn.1000-0801.2014.07.016.

摘要

摘要：对大规模图数据划分算法进行了总结，介绍了并行环境下图计算模型，详述了大规模静态图划分算法和动态图划分算法，归纳了这些算法的优缺点以及适应性。最后，指出了关于大图划分尚未探索的有意义的研究课题。

Abstract

The large-scale graph partitioning algorithms were summarized and graph computing models in the distributed environment were introduced. Firstly the large-scale static graph partitioning algorithms and the dynamic graph partitioning algorithms were discussed. Then the advantages and disadvantages of these algorithms and its adaptability conscientiously were sumed up. Finally

some meaningful research subjects about the distributed graph partition

which have not been explored were pointed out.

关键词

Keywords

references

Dutt S . New faster kernighan-lin-type graph-partitioning algorithms . IEEE/ACM International Conference on IEEE , Santa Clara, CA, USA , 1993 : 370 ～ 377

Fiduccia C M , Mattheyses R M . A linear-time heuristic for improving network partitions . 19th Conference on IEEE , Las Vegas, NV, USA , 1982 : 175 ～ 181

Pothen A , Simon H D , Liou K P . Partitioning sparse matrices with eigenvectors of graphs . IAM Journal on Matrix Analysis and Applications , 1990 , 11 ( 3 ): 430 ～ 452

Karypis G , Kumar V . A fast and high quality multilevel scheme for partitioning irregular graphs . SIAM Journal on scientific Computing , 1998 , 20 ( 1 ): 359 ～ 392

周爽，鲍玉斌，王志刚等． BHP：面向BSP 模型的负载均衡Hash图数据划分．计算机科学与探索， 2014 , 8 ( 1 ): 40 ～ 50

Kalnis P , Khayyat Z , Awara K , et al . Mizan:optimizing graph mining in large parallel systems . http://www.academia.edu/2601716/Mizan_Optimizing_Graph_Mining_in_Large_Parallel_Systems http://www.academia.edu/2601716/Mizan_Optimizing_Graph_Mining_in_Large_Parallel_Systems

Ugander J , Backstrom L . Balanced label propagation for partitioning massive graphs . Proceedings of the sixth ACM International Conference on Web Search and Data Mining . ACM, Rome, Italy , 2013 : 507 ～ 516 .

Khayyat Z , Awara K , Alonazi A , et al . Mizan: a system for dynamic load balancing in large-scale graph processing . Proceedings of the 8th ACM European Conference on Computer Systems , Prague, Czech Republic , 2013

Vaquero L , Cuadrado F , Logothetis D , et al . xdgp: a dynamic graph processing system with adaptive partitioning . http://www.researchgate.net/publication/256423219_xDGP_A_Dynamic_Graph_Processing_System_with_Adaptive_Partitioning http://www.researchgate.net/publication/256423219_xDGP_A_Dynamic_Graph_Processing_System_with_Adaptive_Partitioning

Tsourakakis C E , Gkantsidis C , Radunovic B , et al . Fennel:Streaming Graph Partitioning for Massive Scale Graphs . Microsoft Technical Report MSR-TR-2012-113 , 2012

Karypis G , Kumar V . Metis-unstructured graph partitioning and sparse matrix ordering system ,version 2.0. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.376 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.376

Stanton I, , Kliot G . Streaming graph partitioning for large distributed graphs . Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , Beijing, China , 2012

Dean J , Ghemawat S . MapReduce: simplified data processing on large clusters . Communications of the ACM , 2008 , 51 ( 1 ): 107 ～ 113

White T . Hadoop:The Definitive Guide . OˊReilly Media,Inc , 2012

Condie T , Conway N , Alvaro P , et al . MapReduce Online . NSDI 2010 , San Jose, USA , 2010

Bu Y , Howe B , Balazinska M . et al . HaLoop: efficient iterative data processing on large clusters . Proceedings of the VLDB Endowment , 2010 3 ( 1-2 ): 285 ～ 296

Ekanayake J , Li H , Zhang B , et al . Twister: a runtime for iterative MapReduce . Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing , New York, NY, USA , 2010

Zhang Y , Gao Q , Gao L , et al . Priter: a distributed framework for prioritized iterative computations . Proceedings of the 2nd ACM Symposium on Cloud Computing , San Jose, USA , 2011

Valiant L G . A bridging model for parallel computation . Communications of the ACM , 1990 33 ( 8 ): 103 ～ 111 .

Malewicz G , Austern M H , Bik A J C , et al . Pregel: a system for large-scale graph processing . Proceedings of the 2010 ACM SIGMOD International Conference on Management of data , Snowbird, UT, USA , 2010 : 135 ～ 146

Avery C . Giraph: large-scale graph processing infrastructure on Hadoop . Proceedings of the Hadoop Summit , Santa Clara, USA , 2011

Boyd S P , Vandenberghe L . Vandenberghe L . Cambridge : Cambridge University Press , 2004

Salihoglu S , Widom J . GPS: A Graph Processing System . Stanford University

Bao N T , Suzumura T . Towards highly scalable pregel-based graph processing platform with x10 . Proceedings of the 22nd International Conference on World Wide Web Companion, International World Wide Web Conferences Steering Committee , Seoul, Korea , 2013 : 501 ～ 508

Views

3448

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Comparison of Open-Source Distributed Computing Framework for Big Data

Design of Mobile Internet Big Data User Behavior Analysis Engine Based on Cloud Computing

Architecture design, key technologies, and application research of GPU heterogeneous resource pool platform based on virtualization

Challenges and key technologies of new Ethernet for intelligent computing center

Security access permission authentication simulation of multi-source network big data based on blockchain

Related Author

Ai Fang

Xiong Xu

Bing Liang

Yuzhong Zhang

Yiping Yang

Caixia Tao

Xiaojun Xie

Kang Chen

Related Institution

Nari Technology Development Co., Ltd.

China Mobile Research Institute

Research Institute of China United Network Communications Co., Ltd.

Zhejiang Branch of China United Network Communications Co., Ltd.

China United Network Communications Group Co., Ltd.

⁰