A Practical Parallel Algorithm for Computing Minimum Spanning Tree/Forest with MapReduce
文献类型：会议论文
| 作者 | Jin Chang; Zhiyong Zhong; Le Zhou; Jun Luo; Joshua Zhexue Huang; Shengzhong Feng |
| 出版日期 | 2010 |
| 会议名称 | 2010 International Conference on Future Information Technology (ICFIT 2010) |
| 英文摘要 | Minimum spanning tree (MST) is one of the most studied combinatorial problems and keeps on expanding its application areas. However, traditional MST algorithms face the challenge of costing too much time and space when the graph becomes huge.Thus a variety of algorithms have been developed to optimize the process of finding MST,including many distributed and parallel algorithms. In this paper, we present a simple and practical parallel algorithm for computing minimum spanning tree with MapReduce. MapReduce is a distributed programming framework put forward by google with the ability to process large amount of data in a parallel way. Communication and synchronization cost of parallel algorithms implemented by traditional techniques are eliminated by using it. In addition, the framework works well on cluster composed of commodity machines, especially cloud computing platform. We have done experiments on a cluster of ten node machines, installed with Hadoop software, which is an open source implementation of MapReduce.And the result shows that our algorithm shows good scalability and quite efficient. |
| 收录类别 | 其他 |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/3117]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2010 |
| 推荐引用方式 GB/T 7714 | Jin Chang,Zhiyong Zhong,Le Zhou,et al. A Practical Parallel Algorithm for Computing Minimum Spanning Tree/Forest with MapReduce[C]. 见:2010 International Conference on Future Information Technology (ICFIT 2010). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。