  The effectiveness and scalability of MapReduce-based implementations of
complex data-intensive tasks depend on an even redistribution of data between
map and reduce tasks. In the presence of skewed data, sophisticated
redistribution approaches thus become necessary to achieve load balancing among
all reduce tasks to be executed in parallel. For the complex problem of entity
resolution, we propose and evaluate two approaches for such skew handling and
load balancing. The approaches support blocking techniques to reduce the search
space of entity resolution, utilize a preprocessing MapReduce job to analyze
the data distribution, and distribute the entities of large blocks among
multiple reduce tasks. The evaluation on a real cloud infrastructure shows the
value and effectiveness of the proposed load balancing approaches.
