INROADS- An International Journal of Jaipur National University
Year : 2014, Volume : 3, Issue : 1s
First page : ( 106) Last page : ( 110)
Print ISSN : 2277-4904. Online ISSN : 2277-4912.

An Efficient Round robin Minimum Spanning Tree Algorithm in MapReduce Framework

Sharma Mohit*, Saha Suman**

Dept. of CSE, JUIT, Waknaghat, Solan, H.P., India

*Email: mailtomskaushik@gmail.com

**saha.suman@gmail.com

Online published on 11 March, 2014.

Abstract

Nowadays, a new form of parallel computing - MapReduce framework is widely used for processing terabytes or petabytes of data. In graph, minimum spanning tree problem is an important and most studied problem of combinatorial optimization. When graph becomes very large then it cannot be easily processed by a single machine. MapReduce provides the better way to handle MST problem as compared to other parallel model like, PRAM and BSP. ButMapReduce framework is not suitable for all type of algorithms, e.g. it cannot be used where there is aninteraction between the reducers and the HDFS (global data structure) in between the round processing. Reducers processed data locally. In Round robin MST algorithm we have to maintain a global priority queue implemented by heap, where reducers have to interact in each round with this globally maintained datastructure. In this paper we are developing the MapReduce MST algorithm based on round robin MST algorithm. In our algorithm reducer memory is limited to O (m^1-ε), for small constant ε>0. It takes O(└logn┘) rounds to generate a minimum spanning tree betterthan Ω (log n) lower bounds in PRAM model.

Top

Keywords

MapReduce, Round robin minimum spanning tree algorithm, MST.

Top