Uma Estratégia Eficiente de Treinamento para Programação Genética Aplicada a Deduplicação de Registros

• Davi Guimarães da Silva Instituto Federal de Educação Ciência e Tecnologia do Pará
• Moisés Gomes de Carvalho Universidade Federal do Amazonas
• Duivilly Brito Universidade Federal do Amazonas

DOI: https://doi.org/10.5753/sbbd.2018.22241

Resumo

Programação Genética (PG) é uma técnica utilizada de forma eficaz na deduplicação de registros. Nela faz-se necessário realizar uma etapa de treinamento, em que cada registro é comparado com todos os outros na base de dados, tornando-a custosa. Neste artigo, propomos uma abordagem baseada na combinação de uma técnica de agrupamento e janela deslizante, visando minimizar a quantidade de comparações. Nossos experimentos com dados reais mostram que é possível reduzir o custo de treinamento da PG em até 72.8% comparado ao estado da arte sem uma redução significativa na qualidade das soluções geradas.

Palavras-chave: Deduplicação de registros, programação genética, técnica de agrupamento, janela deslizante

Referências

Baeza-Yates, R. A. and Ribeiro-Neto, B. A. (1999). Modern Information Retrieval. ACM Press/Addison-Wesley., New York, NY, USA. p. 39-48. (KDD 03).

Bianco;, G. D. et al. (2013). Tuning large scale deduplication with reduced effort. In Proceedings International Conference on Scientific and Statistical Database Management, ACM, new york., p. 18:1-18:12. (SSDBM).

Bianco;, G. D. et al. (2016). A practical and effective sampling selection strategy for large scale deduplication. IEEE International Conference on Data Engineering, p. 1518-1519.

Bilenko, M.; Mooney, R. J. (2003). Adaptive Duplicate Detection Using Learnable String Similarity Measures. In: ACM., New York, NY, USA. p. 39-48. (KDD 03).

Carvalho, M. G. et al. (2008a). The impact of parameter setup on a genetic programming approach to record deduplication. S.B.C.; Brazilian Symp. Databases, p.91-105.

Carvalho, M. G. et al. (2008b). Replica identification using genetic programming. In: ACM Symposium on Applied Computing., p. 1801-1806. Carvalho, M. G. et al. (2009). Evolutionary approaches to data integration related problems. Tese. Universidade Federal de Minas Gerais, p. 66-81.

Carvalho, M. G. et al. (2012). A genetic programming approach to record deduplication. IEEE Transactions on Knowledge and Data Engineering; NJ, USA., v.24, p. 399-412.

Fellegi, I. P; Sunter, A. B. (1969). A theory for record linkage. Journal of the American Statistical Association., [S.l.], v.64, n.328, p. 1183-1210.

Jain, A. K. et al. (1999). Data clustering: A review. ACM Computing Surveys. 31(3)8.

Koudas, N. et al. (2006). Record linkage: Similarity measures and algorithms. ACM International Conference on Management of Data., p. 802-803, Chicago, USA.

Ma, K. et al. (2015). Large-scale schema-free data deduplication approach with adaptive sliding window using mapreduce. The Computer Journal, 58, n. 11, p.3187-3201.

Ziv, J. et al. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3) pp. 337-343.