Junções por Similaridade em Espaços Vetoriais Semânticos

• Douglas Rolins de Santana Universidade Federal de Goiás
• Leonardo Andrade Ribeiro Universidade Federal de Goiás

DOI: https://doi.org/10.5753/sbbd_estendido.2022.21857

Resumo

Junção por similaridade retorna todos os pares de objetos cuja similaridade não é menor que um limite especificado. Essa operação é de fundamental importância para limpeza e integração de dados. Uma abordagem popular é adotar uma representação em espaço vetorial e usar cosseno para medir a similaridade de dois vetores. Calcular a similaridade de cosseno em todos os pares de vetores é proibitivamente custoso para grandes conjuntos de dados. Algoritmos de junção de similaridade exploram a esparsidade do espaço vetorial gerado por métodos tradicionais para derivar filtros e, assim, reduzir o espaço de comparação. Avanços recentes no processamento de linguagem natural possibilitaram representações baseadas em vetores semanticamente mais ricos, aumentando assim a qualidade dos resultados. No entanto, tais vetores apresentam características diferentes daquelas geradas por métodos tradicionais. Em particular, esses vetores são densos e possuem menor dimensionalidade. Nesse contexto, apresentamos uma proposta de pesquisa centrada em duas questões principais: 1) como essas características afetam o desempenho dos algoritmos de junção por similaridade existentes?; 2) é possível obter desempenho nesta nova representação comparável aos métodos anteriores mantendo a qualidade dos resultados? Este artigo descreve ainda nossa metodologia de pesquisa, apresenta alguns resultados iniciais e delineia trabalhos futuros.

Palavras-chave: limpeza de dados, integração de dados, aprendizado de máquina para sgbd, processamento de strings, junção por similaridade

Referências

Anastasiu, D. C. and Karypis, G. (2014). L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds. In Proceedings of the ICDE Conference, pages 784-795.

Chaudhuri, S., Ganti, V., and Kaushik, R. (2006). A Primitive Operator for Similarity Joins in Data Cleaning. In Proceedings of the ICDE Conference, page 5.

Devlin, J., Chang, M., Lee, K., and Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4171-4186.

Johnson, J., Douze, M., and Jegou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547.

Li, Y., Li, J., Suhara, Y., Doan, A., and Tan, W. (2020). Deep Entity Matching with Pre-Trained Language Models. Proceedings of the VLDB Endowment, 14(1):50-60.

Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient estimation of word representations in vector space.

Mudgal, S., Li, H., Rekatsinas, T., Doan, A., Park, Y., Krishnan, G., Deep, R., Arcaute, E., and Raghavendra, V. (2018). Deep Learning for Entity Matching: A Design Space Exploration. In Proceedings of the SIGMOD Conference, pages 19-34.

Reimers, N. and Gurevych, I. (2019). Sentence-bert: Sentence embeddings using siamese bert-networks. CoRR, abs/1908.10084.

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

Ribeiro-Júnior, S., Quirino, R. D., Ribeiro, L. A., and Martins, W. S. (2017). Fast Parallel Set Similarity Joins on Many-core Architectures. Journal of Information and Data Management, 8(3):255-270.

Salton, G., Wong, A., and Yang, C. S. (1975). A vector space model for automatic indexing. Commun. ACM, 18(11):613-620.

Suri, S., Ilyas, I. F., R e, C., and Rekatsinas, T. (2021). Ember: No-Code Context Enrichment via Similarity-Based Keyless Joins. Proceedings of the VLDB Endowment, 15(3):699-712.

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is All you Need. In Annual Conference on Neural Information Processing Systems, pages 5998-6008.