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

With 20 EC2 m1.small instances, SSSP and PageRank are performed on
different-size graphs. SSSP is executed with 10 iterations on the three synthetic
graphs SSSP-s, SSSP-m, SSSP-l. Figure 3.5a shows the results of SSSP. The iMap-
Reduce implementation reduces running time to 23.2%, 37.0%, and 38.6% of Hadoop
MapReduce implementations for data set SSSP-s, SSSP-m, and SSSP-l, respectively.
Similarly, PageRank is executed with 10 iterations on the three synthetic graphs
PageRank-s, PageRank-m, and PageRank-l. The results are shown in Figure 3.5b.
Figure 3.6a shows the K-means running time limited in 10 iterations, which
are performed on Last.FM data set and on local cluster with 4 nodes. iMapReduce
achieves about 1.2× speedup over Hadoop. The improvement is less significant than
that is achieved for SSSP or PageRank. Nevertheless, this is under expectation since
the implementation of K-means needs to shuffle static structure data and has to exe-
cute map operations synchronously. Figure 3.6b shows the MPI running time on
local cluster with 4 nodes. MPI is performed on a synthetic matrix (1000 × 1000) for
5 iterations. As shown, iMapReduce can achieve about 10% speedup over Hadoop.

(a)

10,000

MapReduce
iMapReduce

8000

6000

4000

38.6%

2000

37.0%

23.2%

0

SSSP-s SSSP-m SSSP-I

(b)

10,000

MapReduce
iMapReduce

8000

6000

62.9%

4000

61.1%

2000

44.0%

0

PageRank-s PageRank-m PageRank-I

FIGURE 3.5 The running time of SSSP (a) and PageRank (b) on different-size graphs.