Learning Blocking Schemes for Record Linkage

Matthew Michelson, Craig A. KnoblockAAAI 2006

Abstract

Record linkage is a critical task for integrating data across disparate databases, yet it faces significant scalability challenges due to the quadratic complexity of exhaustive comparisons. This paper presents the Blocking Scheme Learner (BSL), a machine learning approach that automatically discovers optimal "blocking" rules. By formulating blocking as a supervised rule-learning problem using a modified Sequential Covering Algorithm, BSL identifies attribute combinations that maximize the reduction of the search space while preserving high match completeness. Evaluations across diverse datasets demonstrate that BSL matches or exceeds the performance of manually crafted expert rules, offering a robust and efficient solution for large-scale data integration.

Introduction: The Scalability Challenge in Record Linkage

Record linkage—the process of identifying records across different databases that refer to the same real-world entity—is fundamental to data integration. However, it suffers from a massive scalability problem. For instance, comparing two datasets with 5,000 records each requires 25 million detailed comparisons in a naive approach.

Example of record linkage between Census and Researcher datasets, where variations in names (e.g., Matt vs. Matthew) complicate matching.

To solve this, researchers use blocking: a preprocessing step that groups similar records into "blocks" and only compares records within the same block. For example, one might only compare people who share the same Zip code. The challenge lies in selecting the right attributes and methods. Overly broad blocking (e.g., matching on State) fails to reduce the search space sufficiently, while overly restrictive blocking (e.g., exact Full Name) misses true matches due to data noise. Historically, these "blocking schemes" were developed through manual trial-and-error or expert intuition.

The BSL Framework: Automated Rule Discovery

The authors propose BSL (Blocking Scheme Learner), which frames blocking as a supervised rule-learning problem. BSL defines a blocking scheme as a disjunction of conjunctions (an "OR" of "ANDs"), such as: (Match on Zip AND First Letter of Last Name) OR (Match on Phone Number).

The core of BSL is a Modified Sequential Covering Algorithm (SCA):

  1. Rule Learning: A greedy beam search identifies {method, attribute} pairs that maximize the Reduction Ratio (RR)—the percentage of unnecessary comparisons eliminated—while maintaining a minimum threshold for Pairs Completeness (PC)—the percentage of true matches retained.
  2. Iterative Covering: Once a rule is learned, covered matches are removed from the training set, and the algorithm seeks new rules for the remaining matches.
  3. Optimization: A "containment check" discards redundant complex rules if a simpler rule covers the same set of matches, ensuring computational efficiency.

Experimental Evaluation

BSL was evaluated on three distinct datasets:

  • Restaurants: A small dataset (54 records) matching records between Fodors and Zagat.
  • Cars: A dataset featuring attributes like make, model, and year.
  • Synthetic Census Data: A large dataset designed to mimic US Census challenges, including eight attributes like name, date of birth, and phone number.

Results and Discussion

BSL consistently matched or outperformed existing methods across all tests. On the Cars dataset, BSL achieved a 99.86% Reduction Ratio, significantly outperforming the manually designed HFM scheme (47.92% RR) while maintaining nearly identical match coverage (~99.9%). On Census data, BSL's learned rules achieved 99.85% PC, slightly better than the "Best Five" rules manually crafted by a renowned census expert (99.16% PC), with only a marginal loss in reduction efficiency.

Performance of BSL on synthetic census data as a function of training data percentage, showing high stability in Reduction Ratio (RR) and increasing Pairs Completeness (PC).

A key finding is BSL's data efficiency. As shown in the figure above, even when trained on only 10% of the available data, the system maintains a very high Reduction Ratio. While Pairs Completeness improves with more data, the performance is robust enough to avoid massive labeling efforts for large datasets, proving its effectiveness in real-world scenarios where labeled data may be scarce.

Conclusion and Future Directions

By treating blocking as a supervised learning problem, BSL discovers non-obvious attribute combinations that optimize the efficiency-accuracy trade-off. Future work aims to explore unsupervised methods, such as "capture-recapture" statistics, to estimate coverage without labeled data, and to integrate more complex clustering methods like canopy clustering into the rule-learning framework.

Summary updated

BibTeX
@inproceedings{michelson2006learning,
  author = {Matthew Michelson and Craig A. Knoblock},
  title = {{Learning Blocking Schemes for Record Linkage}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure