Incremental MapReduce Computations - Large Scale and Big Data: Processing and Management - page 144

(a)

30

Contraction
Task

25

20

15

10

5

0

K-Means WordCount KNN CoMatrix BiCount

Applications

(b)

10

Contraction
Task

8

6

4

2

0.008 0.001

0

K-Means WordCount KNN CoMatrix BiCount

Applications

FIGURE 4.8 Overheads imposed by Incoop in comparison to Hadoop. (a) Performance
overhead for the first job run. (b) Space overhead.

( WordCount , CoMatrix , and BiCount ), the overheads using the Contraction
approach are higher, due to the overheads for processing all levels of the tree of the
contraction phase.
Space overhead. Figure 4.8b shows the space overhead for storing memoized
results as a fraction of the input size. The results show that the contraction approach
requires more space to store the results for all the levels of the tree, as expected.
Overall, space overheads can reach up to 9× ( CoMatrix ), highlighting the trade-off
between space in time that is enabled by this approach.

4.7 RELATED WORK
Several fields and research communities have looked into related problems. In this
section, we present an overview of this body of related work.