Infrastructures and Bounds for Distributed Entity Resolution

Entity resolution (ER), deduplication or record linkage is a computationally hard problem with distributed implemen-tations typically relying on shared memory architectures. We show simple reductions to communication complexity and data streaming lower bounds to illustrate the diculties with a distributed implementation: If the data records are split among servers, then basically all data must be trans-ferred. As a key result, we demonstrate that ER can be solved using algorithms with three dierent distributed computing paradigms: Distributed key-value stores; Map-Reduce; Bulk Synchronous Parallel. We measure our algorithms in the real-world scenario of an insurance customer master data integration procedure. We show how the algorithms can be modied for non-Boolean fuzzy merge functions and similarity indexes. 1