i2MapReduce: Incremental Iterative MapReduce

Cloud intelligence applications often perform iterative computa-tions (e.g., PageRank) on constantly changing data sets (e.g., We-b graph). While previous studies extend MapReduce for efficient iterative computations, it is too expensive to perform an entirely new large-scale MapReduce iterative job to timely accommodate new changes to the underlying data sets. In this paper, we pro-pose i2MapReduce to support incremental iterative computation. We observe that in many cases, the changes impact only a very s-mall fraction of the data sets, and the newly iteratively converged state is quite close to the previously converged state. i2MapReduce exploits this observation to save re-computation by starting from the previously converged state, and by performing incremental up-dates on the changing data. Our preliminary result is quite promis-ing. i2MapReduce sees significant performance improvement over re-computing iterative jobs in MapReduce