A Scalable Parallel Deduplication Algorithm

• Walter Santos UFMG
• Thiago Teixeira UFMG
• Carla Machado UFMG
• Wagner Meira Jr. UFMG
• Renato Ferreira UFAM
• Dorgival Guedes UFMG
• Altigran S. Da Silva UFMG

Resumo

The identification of replicas in a database is fundamental to improve the quality of the information. Deduplication is the task of identifying replicas in a database that refer to the same real world entity. This process is not always trivial, because data may be corrupted during their gathering, storing or even manipulation. Problems such as misspelled names, data truncation, data input in a wrong format, lack of conventions (like how to abbreviate a name), missing data or even fraud may lead to the insertion of replicas in a database. The deduplication process may be very hard, if not impossible, to be performed manually, since actual databases may have hundreds of millions of records. In this paper, we present our parallel deduplication algorithm, called FER- APARDA. By using probabilistic record linkage, we were able to successfully detect replicas in synthetic datasets with more than 1 million records in about 7 minutes using a 20- computer cluster, achieving an almost linear speedup. We believe that our results do not have similar in the literature when it comes to the size of the data set and the processing time.

Palavras-chave: Couplings, Computer science, Scalability, Computer architecture, High performance computing, Demography, Clustering algorithms, Deductive databases, Software libraries, Erbium