Ambiente baseado em contexto para identificação de tuplas duplicadas com recursos de paralelização e meta-heurísticas

Abstract

The problem with the occurrence of non-identical duplicate tuples in a database consists of the existence of records that refer to the same object, but are found under different representations. Duplicate records need to be identified and removed, because they can cause inconsistencies in databases and affect the quality of the knowledge extraction process. However, even though there are algorithms in the scientific literature that can detect and remove duplications, they have to be improved in order to solve current problems. The problems are not considering the data context, the need for in-depth knowledge of the data set in order to use the best similarity function in that case, the NP-Hard complexity of the problem and the characteristics of Big Data repositories. The use of meta-heuristics has shown to be promising to deal with the high complexity of the problem. However, the amount of additional processing for considering the data context and choosing the similarity function automatically leads to an increase in computational cost, which can make the application in large data sets unfeasible. In this scenario, this work aims to create an efficient environment that allows the identification and removal of deduplication in data sets, with automatic similarity function selection according to the context. As a scientific contribution, the environment will allow context consideration of the database in all pre-processing steps, in addition to presenting a parallel approach and in memory, which, in relation to the literature correlates, will allow to maximize the number of deduplication found correctly, reducing processing time, making the application feasible to be used in the Big Data scenario.

O problema da ocorrência de tuplas duplicadas não idênticas em base de dados consiste na existência de registros que se referem a um mesmo objeto, mas que são encontrados sob distintas representações. Por causarem inconsistências nas bases de dados e afetarem a qualidade dos resultados de processos de extração de conhecimento, os registros duplicados precisam ser identificados e removidos. Entretanto, ainda que existam algoritmos na literatura científica que realizam os procedimentos de detecção de duplicações, se fazem necessárias contribuições no sentido de sanar problemas atuais, como a necessidade de profundo conhecimento do conjunto de dados a fim de que seja escolhida uma função de similaridade eficaz, a complexidade NP-Hard do problema e as características do volumosos repositórios de dados do cenário Big Data. As estratégias como a utilização de meta-heurísticas tem se mostrado promissoras para lidar com a alta complexidade do problema, contudo, o volume de processamento adicional dispendido para que o contexto dos dados seja considerado e para que funções de similaridade sejam implementadas, acarreta em aumento do custo computacional, o que tende a inviabilizar a aplicação em grandes conjuntos de dados. Este trabalho tem por objetivo a apresentação de um ambiente eficiente que permita a identificação de tuplas duplicadas não idênticas, com utilização de mais de uma única função de similaridade. Como contribuição científica, tem-se um ambiente capaz de considerar o contexto de cada base de dados em todas as etapas de pré-processamento, com apoio de Algoritmos Genéticos na identificação de duplicações, além de apresentar uma abordagem paralela e em memória. Tais ingredientes considerados, em relação aos correlatos da literatura, oferecem a possibilidade de maximizar a quantidade de tuplas duplicadas não idênticas encontradas e consequente redução do tempo de processamento aplicados a grandes bancos de dados.