Fisher, J. ; Christen, P. ; Wang, Q. ; Rahm, E.

A Clustering-Based Framework to Control Block Sizes for Entity Resolution

Proc. 21st ACM SIGKDD Conf. on Knowledge Discovery and Mining (KDD), 279-288, 2015

2015 / 08

Paper

Futher information: http://dx.doi.org/10.1145/2783258.2783396

Abstract

Entity resolution (ER) is a common data cleaning task that involves determining which records from one or more data sets refer to the same real-world entities. Because a pairwise comparison of all records scales quadratically with the number of records in the data sets to be matched, it is common to use blocking or indexing techniques to reduce the number of comparisons required. These techniques split the data sets into blocks and only records within blocks are compared with each other. Most existing blocking techniques do not provide control over the size of the generated blocks, despite its importance in many practical applications of ER, such as privacy-preserving record linkage and real-time ER.We propose two novel hierarchical clustering approaches which can generate blocks within a specified size range, and we present a penalty function which allows control of the trade-off between block quality and block size in the clustering process. We evaluate our techniques on three real-world data sets and compare them against three baseline approaches, standard blocking, Soundex encoding and sorted neighbourhood based indexing. Our results show that the proposed techniques perform well on the measures of pairs completeness and reduction ratio compared with the baseline approaches, while achieving the required block size restrictions.