Incremental recomputations in MapReduce

Abstract

This paper explores the application of view maintenance techniques in a MapReduce environment. Abstractly, a MapReduce program can be seen as a view definition and the computed result as a materialized view. As yet, MapReduce programs need to be re-executed to obtain up-to-date results after base data has changed, i.e. the view is recomputed from scratch. We present a case study based on typical MapReduce programs mentioned in Google's original MapReduce paper. By adapting view maintenance techniques, we were able to recompute results in an incremental fashion considerably more efficiently. Based on the case study, we develop a general solution for the incremental maintenance of the class of MapReduce programs that compute self-maintainable aggregates.