Entity Resolution y Deduplication con Blocking paralelo en Spark

Abstract

En este trabajo planteamos un algoritmo que permite identificar qué registros de un dataset, aún no siendo idénticos, se corresponden con la misma entidad real (Entity Resolution). El algoritmo clásico para este proceso consiste en la comparación directa de todos los registros dos a dos y, por tanto, tiene por lo menos complejidad cuadrática. Nuestra solución mejora el algoritmo clásico utilizando paralelización y, por consiguiente, garantizando la escalabilidad del mismo. Además, el diseño del algoritmo es genérico. Permite la definición de unos parámetros de configuración para adaptarlo al dataset concreto que se desee estudiar. Las ejecuciones realizadas para analizar el comportamiento de este algoritmo han resultado muy satisfactorias, obteniendo resultados muy similares al caso clásico en unos tiempos de ejecución significativamente menores. Esta diferencia temporal es aún mayor conforme aumentemos el tamaño de los datasets sobre la que se trabajen.

In this work we present and algorithm that allows the user to identify which registers from a dataset, while not being identical, represent the same real-world entity (Entity Resolution). The classical algorithm for this process consists of direct comparisons between all registers and, as a result, has at least quadratic complexity. Our solution improves upon this classical algorithm by using parallelization, granting its scalability. In addition, its design is generic. It allows for some configuration parameters to be defined depending on the concrete dataset that wants to be studied. The executions performed to analyse its behaviour have been very successful, obtaining very similar results to the classical algorithm using significantly less execution time. This time difference is even bigger as the dataset’s size increases.