Além do fgssjoin: Algoritmos Paralelos para Junções por Similaridade de Conjuntos

• Rafael David Quirino UFG
• Wellington Santos Martins UFG

DOI: https://doi.org/10.5753/erigo.2022.227677

Resumo

Junções por similaridade de conjuntos são operações de grande importância nos sistemas modernos de bancos de dados, especialmente para os chamados armazens de dados, onde várias operações rotineiras como integração, limpeza e mineração de dados as utilizam com frequência. Algoritmos exatos, que retornam todos os pares similares possíveis de acordo com algum limiar de similaridade são computacionalmente caros, o que impõe lentidão a cargas de trabalho analíticas e destaca a necessidade de soluções paralelas para o problema. Trabalhos recentes apresentam algoritmos paralelos voltados para dispositivos de arquitetura many-core como as GPUs. Nesse artigo apresentamos um novo algoritmo para a etapa de filtragem do fgssjoin, um algoritmo paralelo conhecido, baseado em gpu, para a junção exata por similaridade de conjuntos.

Referências

Bayardo, R. J., Ma, Y., and Srikant, R. (2007). Scaling up All Pairs Similarity Search. In WWW, pages 131–140.

Chaudhuri, S., Ganti, V., and Kaushik, R. (2006). A primitive operator for similarity joins in data cleaning. In ICDE, page 5.

Cruz, M. S. H., Kozawa, Y., Amagasa, T., and Kitagawa, H. (2015). GPU Acceleration of Set Similarity Joins. In DEXA, pages 384–398.

Doan, A., Halevy, A. Y., and Ives, Z. G. (2012). Principles of Data Integration. Morgan Kaufmann.

Leskovec, J., Rajaraman, A., and Ullman, J. D. (2014). Mining of Massive Datasets, 2nd Ed. Cambridge University Press.

Quirino, R. D., Ribeiro-Júnior, S., Ribeiro, L. A., and Martins, W. S. (2017). fgssjoin: A gpu-based algorithm for set similarity joins. In Hammoudi, S., Smialek, M., Camp, O., and Filipe, J., editors, ICEIS 2017 - Proceedings of the 19th International Con- ference on Enterprise Information Systems, Volume 1, Porto, Portugal, April 26-29, 2017, pages 152–161. SciTePress.

Ribeiro, L. A. and Harder, T. (2011). Generalizing Prefix Filtering to Improve Set Similarity Joins. Information Systems, 36(1):62–78.

Sarawagi, S. and Kirpal, A. Efficient Set Joins on Similarity Predicates. In SIGMOD.

Vernica, R., Carey, M. J., and Li, C. (2010). Efficient Parallel Set-similarity Joins using MapReduce. In SIGMOD, pages 495–506.

Wang, J., Li, G., and Feng, J. (2012). Can We Beat the Prefix Filtering?: An Adaptive Framework for Similarity Join and Search. In SIGMOD, pages 85–96.

Xiao, C., Wang, W., Lin, X., Yu, J. X., and Wang, G. (2011). Efficient Similarity Joins for Near-duplicate Detection. TODS, 36(3):15.