DiveScan: um módulo para Recuperação de dados por Similaridade com Diversidade em Postgres

• Anna Júlia Costa Lauton Universidade de São Paulo (USP)
• Agma Juci Machado Traina Universidade de São Paulo (USP) https://orcid.org/0000-0003-4929-7258
• Caetano Traina Jr. Universidade de São Paulo (USP) https://orcid.org/0000-0002-6625-6047

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

Resumo

Consultas por similaridade com diversidade são úteis em aplicações que demandam resultados que evitam redundâncias, como no diagnóstico médico, sistemas de recomendação e busca por imagens. Entretanto, os Sistemas de Gerenciamento de Bases de Dados (SGBDs) ainda oferecem suporte limitado a consultas desse tipo. Este trabalho apresenta o módulo DiveScan, uma extensão para o SGBD Postgres que executa tais consultas com os algoritmos FM ou BRID, e pode utilizar índices GiST para acelerar a busca. A avaliação experimental indica que a abordagem indexada supera a varredura sequencial em diferentes cenários, reduzindo significativamente o tempo de execução.

Palavras-chave: Consultas por similaridade, Diversificação de Resultados, Postgres, Indexação, GiST R-tree

Referências

Chandrasekaran, D. and Mago, V. (2021). Evolution of semantic similarity—a survey. ACM Comput. Surv., 54(2):Article 41.

Eleutério, I. A. R., Cazzolato, M. T., Teixeira, L. R., Gutierrez, M. A., Traina, A. J. M., and Traina-Jr., C. (2024). Migue-sim: Speeding up similarity queries with native rdbms resources. In Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing, pages 321–328, New York, NY, USA. Association for Computing Machinery.

Gupta, S., Thakar, U., and Tokekar, S. (2025). A comprehensive survey on techniques for numerical similarity measurement. Expert Systems with Applications, 277:127235.

Hambarde, K. A. and Proença, H. (2023). Information retrieval: Recent advances and beyond. IEEE Access, 11:76581–76604.

Hellerstein, J. M., Naughton, J. F., and Pfeffer, A. (1995). Generalized search trees for database systems. In Dayal, U., Gray, P. M. D., and Nishio, S., editors, International Conference on Very Large Databases (VLDB), pages 562–573, Zurich, Switzerland. Morgan Kaufmann.

Jasbick, D., Santos, L., de Oliveira, D., and Bedo, M. (2020). Some branches may bear rotten fruits: Diversity browsing vp-trees. In Similarity Search and Applications, pages 140–154. Springer.

Santos, L. F. D., Oliveira, W. D. d., Ferreira, M. R. P., Traina, A. J. M., and Traina Jr, C. (2013). Parameter-free and domain-independent similarity search with diversity. In Szalay, A., Budavari, T., Balazinska, M., Meliou, A., and Sacan, A., editors, 25th International Conference on Scientific and Statistical Database Management - SSDBM’2013, pages 5–16, Baltimore, MD, USA. ACM.

Shu, X. and Ye, Y. (2023). Knowledge discovery: Methods from data mining and machine learning. Social Science Research, 110:102817.

Skopal, T., Dohnal, V., Batko, M., and Zezula, P. (2009). Distinct nearest neighbors queries for similarity search in very large multimedia databases. In Chan, C. Y. and Mitra, P., editors, 11th ACM International Workshop on Web Information and Data Management WIDM 2009, pages 11–14, Hong Kong, China. ACM.

Traina-Jr., C., Moriyama, A., Rocha, G., Cordeiro, R., Ciferri, C. D. A., and Traina, A. (2019). The similarql framework: Similarity queries in plain SQL. In Proceedings of the ACM Symposium on Applied Computing, Limassol, Cyprus. ACM.

Weber, M., Silva-Leite, J., Santos, L., de Oliveira, D., and Bedo, M. (2024). Adicionando suporte à diversificação de resultados em índices hnsw considerando espaços de baixa e alta dimensionalidade. In Anais do XXXIX Simpósio Brasileiro de Bancos de Dados, pages 14–26. SBC.

Yang, P., Wang, H., Yang, J., Qian, Z., Zhang, Y., and Lin, X. (2024). Deep learning approaches for similarity computation: A survey. IEEE Transactions on Knowledge and Data Engineering, 36(12):7893–7912.