iMapReduce - Large Scale and Big Data: Processing and Management - page 106

3 iMapReduce

Extending MapReduce
for Iterative Processing

Yanfeng Zhang, Qixin Gao,
Lixin Gao, and Cuirong Wang

CONTENTS
3.1 Iterative Algorithms in MapReduce ............................................................. 108
3.1.1 MapReduce Overview ...................................................................... 108
3.1.2 Examples of Implementing Iterative Algorithms in MapReduce ..... 109
3.1.2.1 PageRank ........................................................................... 109
3.1.2.2 K-means ............................................................................. 110
3.1.2.3 Matrix Power Iteration ....................................................... 110
3.1.3 Properties of Iterative Computations in MapReduce........................ 111
3.1.4 Limited Support of Iterative Computations by MapReduce ............. 112
3.2 Programming Model .................................................................................... 113
3.3 System Design .............................................................................................. 115
3.3.1 Overview ........................................................................................... 115
3.3.2 Iterative Processing ........................................................................... 116
3.3.2.1 Persistent Tasks .................................................................. 116
3.3.2.2 Passing State Data from Reduce to Map ........................... 117
3.3.2.3 Joining State Data with Structure Data ............................. 117
3.3.2.4 Asynchronous Execution of Map Tasks............................. 117
3.3.3 Iteration Termination ........................................................................ 118
3.3.4 Fault Tolerance .................................................................................. 118
3.3.5 Load Balancing ................................................................................. 119
3.4 Algorithm Implementation ........................................................................... 119
3.4.1 iMapReduce API .............................................................................. 119
3.4.2 PageRank Implementation Example................................................. 120
3.5 Performance .................................................................................................. 121
3.6 Related Work ................................................................................................ 123
3.7 Summary ...................................................................................................... 125
Acknowledgments .................................................................................................. 125
References .............................................................................................................. 125

107