A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication

TLDR

Record linkage matches records across databases, while deduplication removes duplicates within a single database; as data volumes grow, matching becomes computationally challenging, prompting the development of indexing techniques, yet no comprehensive survey has been published. The survey aims to evaluate indexing techniques that reduce comparison pairs while preserving high matching quality. The authors survey 12 variants of six indexing methods, analyze their complexity, and assess performance and scalability through experiments on synthetic and real datasets. The evaluation shows that indexing techniques differ in complexity and scalability, with some achieving substantial reductions in comparison pairs while maintaining matching quality.

Abstract

Record linkage is the process of matching records from several databases that refer to the same entities. When applied on a single database, this process is known as deduplication. Increasingly, matched data are becoming important in many application areas, because they can contain information that is not available otherwise, or that is too costly to acquire. Removing duplicate records in a single database is a crucial step in the data cleaning process, because duplicates can severely influence the outcomes of any subsequent data processing or data mining. With the increasing size of today's databases, the complexity of the matching process becomes one of the major challenges for record linkage and deduplication. In recent years, various indexing techniques have been developed for record linkage and deduplication. They are aimed at reducing the number of record pairs to be compared in the matching process by removing obvious nonmatching pairs, while at the same time maintaining high matching quality. This paper presents a survey of 12 variations of 6 indexing techniques. Their complexity is analyzed, and their performance and scalability is evaluated within an experimental framework using both synthetic and real data sets. No such detailed survey has so far been published.