Entity Resolution with Recursive Blocking

摘要

Entity resolution is a well-known challenge in data management for the lack of unique identifiers of records and various errors hidden in the data, undermining the identifiability of entities they refer to. To reveal matching records, every record potentially needs to be compared with all other records in the database, which is computationally intractable even for moderately-sized databases. To circumvent this quadratic challenge, blocking methods are typically employed to facilitate restricting promising comparisons of pairs within small subsets, called blocks, of records. Existing effective methods typically rely on blocking keys created by experts to capture matches, which inevitably involves a large amount of human labor and do not guarantee high-quality results. To reduce manual labor and promote accuracy, machine learning approaches are investigated to meet the challenge with limited success, due to high requirements of training data and inefficiency, especially for large databases. The exhaustive method produces exact results but suffers from efficiency problems. In this paper, we propose a paradigm of divide-and-conquer entity resolution, named recursive blocking, which derives comparatively good results while largely alleviating efficiency concerns. Specifically, recursive blocking refines blocks and traps matches in an iterative fashion to derive high-quality results, and we study two types of recursive blocking, i.e. redundancy- and partition-based approaches, and investigate their relative performance. Comprehensive experiments on both real-world and synthetic datasets verified the superiority of our approaches over the existing ones. (C) 2020 Elsevier Inc. All rights reserved.