大规模图数据划分算法综述

许金凤; 董一鸿; 王诗懿; 何贤芒; 陈华辉

doi:10.3969/j.issn.1000-0801.2014.07.016

您当前的位置：

首页 >

文章列表页 >

大规模图数据划分算法综述

综述 | 更新时间：2024-06-05

- 大规模图数据划分算法综述
- Summary of Large-Scale Grapb Partitioning Algoritbms
- 电信科学 2014年30卷第7期页码：100-106
- 作者机构：
- 作者简介：
  
  [ "许金凤，女，宁波大学硕士生，主要研究方向为大数据、数据挖掘。" ]
  [ "董一鸿，男，博士，宁波大学教授，主要研究方向为大数据、数据挖掘和人工智能。" ]
  [ "王诗懿，女，宁波大学硕士生，主要研究方向为大数据、数据挖掘。" ]
  [ "何贤芒，男，宁波大学讲师，主要研究方向为大数据、数据挖掘、隐私保护。" ]
  [ "陈华辉，男，博士，宁波大学教授，主要研究方向为数据流与数据挖掘。" ]
- 基金信息：
  
  宁波市自然科学基金资助项目(61202007);宁波市自然科学基金资助项目(2013A610063)
- DOI：10.3969/j.issn.1000-0801.2014.07.016
  中图分类号：
- 网络出版日期：2014-07，
  
  纸质出版日期：2014-07-20
- 稿件说明：
移动端阅览
许金凤, 董一鸿, 王诗懿, 等. 大规模图数据划分算法综述[J]. 电信科学, 2014,30(7):100-106.

Jinfeng Xu, Yihong Dong, Shiyi Wang, et al. Summary of Large-Scale Grapb Partitioning Algoritbms[J]. Telecommunications science, 2014, 30(7): 100-106.
许金凤, 董一鸿, 王诗懿, 等. 大规模图数据划分算法综述[J]. 电信科学, 2014,30(7):100-106. DOI： 10.3969/j.issn.1000-0801.2014.07.016.

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

浏览量

3448

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

主流大数据处理开源架构的分析及对比评测

基于云计算的移动互联网大数据用户行为分析引擎设计

基于虚拟化的GPU异构资源池平台架构设计、关键技术及应用研究

面向智算中心的新型以太网需求与关键技术

基于区块链的多源网络大数据安全访问权限认证仿真