Data Integration

Dedoop: efficient deduplication with Hadoop

Authors: 
Kolb, L; Thor, A; Rahm, E

We demonstrate a powerful and easy-to-use tool called Dedoop (Deduplication with Hadoop) for MapReduce-based entity resolution (ER) of large datasets. Dedoop supports a browser-based specification of complex ER workflows including blocking and matching steps as well as the optional use of machine learning for the automatic generation of match classifiers. Specified workflows are automatically translated into MapReduce jobs for parallel execution on different Hadoop clusters. To achieve high performance Dedoop supports several advanced load balancing strategies.

Year: 
2012

Fuzzy Joins Using MapReduce

Authors: 
Afrat, Foto N.; Sarma, Anish Das; Menestrina, David; Parameswaran, Aditya; Ullman, Jeffrey D.

Abstract—Fuzzy/similarity joins have been widely studied in the research community and extensively used in real-world applications. This paper proposes and evaluates several algorithms for finding all pairs of elements from an input set that meet a similarity threshold. The computation model is a single MapReduce job. Because we allow only one MapReduce round, the Reduce function must be designed so a given output pair is produced by only one task; for many algorithms, satisfying this condition is one of the biggest challenges.

Year: 
2012

Load Balancing for MapReduce-based Entity Resolution

Authors: 
Kolb, L; Thor, A; Rahm, E

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.

Year: 
2012

Learning-based Entity Resolution with MapReduce

Authors: 
Kolb, L; Köpcke, H; Thor, A; Rahm, E

Entity resolution is a crucial step for data quality and data
integration. Learning-based approaches show high effective-
ness at the expense of poor efficiency. To reduce the typ-
ically high execution times, we investigate how learning-
based entity resolution can be realized in a cloud infras-
tructure using MapReduce. We propose and evaluate two
efficient MapReduce-based strategies for pair-wise similar-
ity computation and classifier application on the Cartesian
product of two input sources. Our evaluation is based on
real-world datasets and shows the high efficiency and effec-

Year: 
2011

Block-based Load Balancing for Entity Resolution with MapReduce

Authors: 
Kolb, L; Thor, A; Rahm, E

The effectiveness and scalability of MapReduce-based im-
plementations 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 balanc-
ing among all reduce tasks to be executed in parallel. For
the complex problem of entity resolution with blocking, we
propose BlockSplit, a load balancing approach that supports
blocking techniques to reduce the search space of entity res-

Year: 
2011

Multi-pass sorted neighborhood blocking with MapReduce

Authors: 
Kolb, L; Thor, A; Rahm, E

Abstract Cloud infrastructures enable the efficient parallel
execution of data-intensive tasks such as entity resolution on
large datasets. We investigate challenges and possible solu-
tions of using the MapReduce programming model for par-
allel entity resolution using Sorting Neighborhood blocking
(SN). We propose and evaluate two efficient MapReduce-
based implementations for single- and multi-pass SN that
either use multiple MapReduce jobs or apply a tailored data
replication. We also propose an automatic data partitioning
approach for multi-pass SN to achieve load balancing. Our

Year: 
2011

MapDupReducer: Detecting Near Duplicates over Massive Datasets

Authors: 
Wang, Chaokun; Wang, Jianmin; Lin, Xuemin; Wang, Wei, Wang, Haixun; Li, Hongsong; Tian, Wanpeng; Xu, Jun; Li, Rui

Near duplicate detection benefits many applications, e.g.,
on-line news selection over the Web by keyword search. The
purpose of this demo is to show the design and implemen-
tation of MapDupReducer, a MapReduce based system ca-
pable of detecting near duplicates over massive datasets ef-
ficiently.

Year: 
2010

Parallel Sorted Neighborhood Blocking with MapReduce

Authors: 
Kolb, L; Thor, A; Rahm, E

Cloud infrastructures enable the efficient parallel execution of data-intensive
tasks such as entity resolution on large datasets. We investigate challenges and possi-
ble solutions of using the MapReduce programming model for parallel entity resolu-
tion. In particular, we propose and evaluate two MapReduce-based implementations
for Sorted Neighborhood blocking that either use multiple MapReduce jobs or apply
a tailored data replication.

Year: 
2011

Efficient Parallel Set-Similarity Joins Using MapReduce

Authors: 
Vernica, Rares; Carey, Michael J.; Li, Chen

In this paper we study how to efficiently perform set-simi-
larity joins in parallel using the popular MapReduce frame-
work. We propose a 3-stage approach for end-to-end set-
similarity joins. We take as input a set of records and output
a set of joined records based on a set-similarity condition.
We efficiently partition the data across nodes in order to
balance the workload and minimize the need for replication.
We study both self-join and R-S join cases, and show how to
carefully control the amount of data kept in main memory

Year: 
2010
Syndicate content