Name
Abstract | ||
|---|---|---|
Many online data sets evolve over time as new entries are slowly added and existing entries are deleted or modified. Taking advantage of this, systems for incremental bulk data processing, such as Google's Percolator, can achieve efficient updates. To achieve this efficiency, however, these systems lose compatibility with the simple programming models offered by non-incremental systems, e.g., MapReduce, and more importantly, requires the programmer to implement application-specific dynamic algorithms, ultimately increasing algorithm and code complexity. In this paper, we describe the architecture, implementation, and evaluation of Incoop, a generic MapReduce framework for incremental computations. Incoop detects changes to the input and automatically updates the output by employing an efficient, fine-grained result reuse mechanism. To achieve efficiency without sacrificing transparency, we adopt recent advances in the area of programming languages to identify the shortcomings of task-level memoization approaches, and to address these shortcomings by using several novel techniques: a storage system, a contraction phase for Reduce tasks, and an affinity-based scheduling algorithm. We have implemented Incoop by extending the Hadoop framework, and evaluated it by considering several applications and case studies. Our results show significant performance improvements without changing a single line of application code. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2038916.2038923 | SoCC |
Keywords | DocType | Citations |
code complexity,incoop detects change,hadoop framework,application code,affinity-based scheduling algorithm,incremental bulk data processing,application-specific dynamic algorithm,generic mapreduce framework,incremental computation,efficient updates,programming language,scheduling algorithm,memoization,stability,data processing,storage system,programming model | Conference | 140 |
PageRank | References | Authors |
5.59 | 18 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pramod Bhatotia | 1 | 414 | 28.94 |
| Alexander Wieder | 2 | 245 | 11.43 |
| Rodrigo Rodrigues | 3 | 1049 | 53.56 |
| Umut A. Acar | 4 | 716 | 45.83 |
| Rafael Pasquin | 5 | 140 | 5.59 |