Consultas analíticas por similaridade em SGBD Relacionais
Resumo
A grande variedade de dados complexos produzidos nos últimos tempos, para os quais as buscas por igualdade tem pouca utilidade, levou ao desenvolvimento de operações de consulta baseadas em similaridade. Entretanto, poucos trabalhos consideram o tratamento da similaridade no contexto de processamento analítico online. Neste trabalho apresenta-se uma abordagem para a execução de consultas ad hoc analíticas, onde o critério de agrupamento pode ser baseado na similaridade, em especial nos contextos métrico, espacial e temporal. O protótipo desenvolvido para validar e ilustrar os conceitos mostra que esse critério pode ser executado em diferentes níveis de granularidade, por meio de recursos da linguagem padrão SQL em Sistemas de Gerenciamento de Bancos de Dados Relacionais.
Palavras-chave:
consultas analíticas, similaridade, cubos OLAP
Referências
Abelló, A. and Romero, O. (2018). Online analytical processing. In Encyclopedia of Database Systems, pages 2558–2563. Springer. DOI: 10.1007/978-1-4614-8265-9_252.
Barioni, M. C. N., Razente, H., Traina, A., and Traina-Jr, C. (2008). Accelerating k-medoid-based algorithms through metric access methods. J. Syst. Softw., 81(3):343–355. DOI: 10.1016/J.JSS.2007.06.019.
Barioni, M. C. N., Razente, H., Traina, A., and Traina-Jr., C. (2009). Seamlessly integrating similarity queries in SQL. Softw. Pract. Exp., 39(4):355–384. DOI: 10.1002/SPE.898.
Chen, L., Gao, Y., Song, X., Li, Z., Zhu, Y., Miao, X., and Jensen, C. S. (2023). Indexing metric spaces for exact similarity search. ACM Comput. Surv., 55(6):128:1–128:39. DOI: 10.1145/3534963.
Eleutério, I., Cazzolato, M., Gutierrez, M. A., Teixeira, L., Traina, A., and Traina-Jr, C. (2024). Migue-sim: Speeding up similarity queries with native rdbms resources. In Symp. Applied Computing (SAC), pages 321–328. DOI: 10.1145/3605098.3636019.
Ezugwu, A., Ikotun, A., Oyelade, O., Abualigah, L., Agushaka, J., Eke, C., and Akinyelu, A. (2022). A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Eng. Appl. Artif. Intell., 110:104743. DOI: 10.1016/J.ENGAPPAI.2022.104743.
Garcia-Alvarado, C. and Ordonez, C. (2015). Clustering binary cube dimensions to compute relaxed GROUP BY aggregations. Inf. Syst., 53:41–59. DOI: 10.1016/j.is.2014.12.008.
Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart, D., Venkatrao, M., Pellow, F., and Pirahesh, H. (1997). Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub totals. Data Min. Knowl. Discov., 1(1):29–53. DOI: 10.1023/A:1009726021843.
Iqbal, M., Lissandrini, M., and Pedersen, T. B. (2022). A foundation for spatio-textualtemporal cube analytics. Inf. Syst., 108:102009. DOI: 10.1016/j.is.2022.102009.
ISO (1992). ISO/IEC 9075:1992: Information technology — Database languages — SQL. International Org. Standardization. [link].
ISO (2023). ISO/IEC 9075:2023: Information technology — Database languages — SQL. International Org. Standardization. [link].
Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognit. Lett., 31(8):651–666. DOI: 10.1016/J.PATREC.2009.09.011.
Kaster, D. S., Bugatti, P. H., Traina, A. J. M., and Traina-Jr, C. (2010). FMI-SiR: A flexible and efficient module for similarity searching on Oracle database. J. Inf. Data Manag., 1(2):229–244. DOI: 10.5753/jidm.2010.1263.
Kelly, M., Longjohn, R., and Nottingham, K. (2024). The UCI Machine Learning Repository. [link].
Kim, T., Li, W., Behm, A., Cetindil, I., Vernica, R., Borkar, V. R., Carey, M. J., and Li, C. (2020). Similarity query support in big data management systems. Inf. Syst., 88. DOI: 10.1016/J.IS.2019.101455.
Lu, W., Hou, J., Yan, Y., Zhang, M., Du, X., and Moscibroda, T. (2017). MSQL: efficient similarity search in metric spaces using SQL. VLDB J., 26(6):829–854. DOI: 10.1007/s00778-017-0481-6.
Matiazzo, M. A. L., de Castro-Silva, V., Oyamada, R. S., and Kaster, D. S. (2023). The dataset-similarity-based approach to select datasets for evaluation in similarity retrieval. In Intl Conf. Similarity Search and Applications (SISAP), volume 14289 of LNCS, pages 125–132. Springer. DOI: 10.1007/978-3-031-46994-7_11.
Oliveira, W. D., Lauton, A. J. C., Traina-Jr, C., and Santos, L. F. D. (2023). Similarity grouping by influence: Exploring result diversification in similarity group-by operators. In Simpósio Brasileiro de Bancos de Dados (SBBD), pages 402–407. SBC. DOI: 10.5753/sbbd.2023.233430.
Razente, H., Barioni, M. C. N., Traina, A., Faloutsos, C., and Traina-Jr, C. (2008). A novel optimization approach to efficiently process aggregate similarity queries in metric access methods. In Int’l Conf. Information and Knowledge Management (CIKM), pages 193–202. ACM. DOI: 10.1145/1458082.1458110.
Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. San Francisco, CA.
Silva, Y. N., Aref,W. G., and Ali, M. H. (2009a). Similarity group-by. In Int’l Conf. Data Engineering (ICDE), pages 904–915. IEEE. DOI: 10.1109/ICDE.2009.113.
Silva, Y. N., Arshad, M. U., and Aref, W. G. (2009b). Exploiting similarity-aware grouping in decision support systems. In Int’l Conf. Extending Database Technology (EDBT), volume 360, pages 1144–1147. ACM. DOI: 10.1145/1516360.1516499.
Silva, Y. N., Sandoval, M., Prado, D., Wallace, X., and Rong, C. (2019). Similarity grouping in big data systems. In Intl Conf. Similarity Search and Applications (SISAP), volume 11807 of LNCS, pages 212–220. Springer. DOI: 10.1007/978-3-030-32047-8_19.
Stonebraker, M. and Pavlo, A. (2024). What goes around comes around... and around... SIGMOD Rec., 53(2):21–37.
Tang, M., Tahboub, R. Y., Aref, W. G., Atallah, M. J., Malluhi, Q. M., Ouzzani, M., and Silva, Y. N. (2016). Similarity group-by operators for multidimensional relational data. IEEE Trans. Knowl. Data Eng., 28(2):510–523. DOI: 10.1109/TKDE.2015.2480400.
Barioni, M. C. N., Razente, H., Traina, A., and Traina-Jr, C. (2008). Accelerating k-medoid-based algorithms through metric access methods. J. Syst. Softw., 81(3):343–355. DOI: 10.1016/J.JSS.2007.06.019.
Barioni, M. C. N., Razente, H., Traina, A., and Traina-Jr., C. (2009). Seamlessly integrating similarity queries in SQL. Softw. Pract. Exp., 39(4):355–384. DOI: 10.1002/SPE.898.
Chen, L., Gao, Y., Song, X., Li, Z., Zhu, Y., Miao, X., and Jensen, C. S. (2023). Indexing metric spaces for exact similarity search. ACM Comput. Surv., 55(6):128:1–128:39. DOI: 10.1145/3534963.
Eleutério, I., Cazzolato, M., Gutierrez, M. A., Teixeira, L., Traina, A., and Traina-Jr, C. (2024). Migue-sim: Speeding up similarity queries with native rdbms resources. In Symp. Applied Computing (SAC), pages 321–328. DOI: 10.1145/3605098.3636019.
Ezugwu, A., Ikotun, A., Oyelade, O., Abualigah, L., Agushaka, J., Eke, C., and Akinyelu, A. (2022). A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Eng. Appl. Artif. Intell., 110:104743. DOI: 10.1016/J.ENGAPPAI.2022.104743.
Garcia-Alvarado, C. and Ordonez, C. (2015). Clustering binary cube dimensions to compute relaxed GROUP BY aggregations. Inf. Syst., 53:41–59. DOI: 10.1016/j.is.2014.12.008.
Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart, D., Venkatrao, M., Pellow, F., and Pirahesh, H. (1997). Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub totals. Data Min. Knowl. Discov., 1(1):29–53. DOI: 10.1023/A:1009726021843.
Iqbal, M., Lissandrini, M., and Pedersen, T. B. (2022). A foundation for spatio-textualtemporal cube analytics. Inf. Syst., 108:102009. DOI: 10.1016/j.is.2022.102009.
ISO (1992). ISO/IEC 9075:1992: Information technology — Database languages — SQL. International Org. Standardization. [link].
ISO (2023). ISO/IEC 9075:2023: Information technology — Database languages — SQL. International Org. Standardization. [link].
Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognit. Lett., 31(8):651–666. DOI: 10.1016/J.PATREC.2009.09.011.
Kaster, D. S., Bugatti, P. H., Traina, A. J. M., and Traina-Jr, C. (2010). FMI-SiR: A flexible and efficient module for similarity searching on Oracle database. J. Inf. Data Manag., 1(2):229–244. DOI: 10.5753/jidm.2010.1263.
Kelly, M., Longjohn, R., and Nottingham, K. (2024). The UCI Machine Learning Repository. [link].
Kim, T., Li, W., Behm, A., Cetindil, I., Vernica, R., Borkar, V. R., Carey, M. J., and Li, C. (2020). Similarity query support in big data management systems. Inf. Syst., 88. DOI: 10.1016/J.IS.2019.101455.
Lu, W., Hou, J., Yan, Y., Zhang, M., Du, X., and Moscibroda, T. (2017). MSQL: efficient similarity search in metric spaces using SQL. VLDB J., 26(6):829–854. DOI: 10.1007/s00778-017-0481-6.
Matiazzo, M. A. L., de Castro-Silva, V., Oyamada, R. S., and Kaster, D. S. (2023). The dataset-similarity-based approach to select datasets for evaluation in similarity retrieval. In Intl Conf. Similarity Search and Applications (SISAP), volume 14289 of LNCS, pages 125–132. Springer. DOI: 10.1007/978-3-031-46994-7_11.
Oliveira, W. D., Lauton, A. J. C., Traina-Jr, C., and Santos, L. F. D. (2023). Similarity grouping by influence: Exploring result diversification in similarity group-by operators. In Simpósio Brasileiro de Bancos de Dados (SBBD), pages 402–407. SBC. DOI: 10.5753/sbbd.2023.233430.
Razente, H., Barioni, M. C. N., Traina, A., Faloutsos, C., and Traina-Jr, C. (2008). A novel optimization approach to efficiently process aggregate similarity queries in metric access methods. In Int’l Conf. Information and Knowledge Management (CIKM), pages 193–202. ACM. DOI: 10.1145/1458082.1458110.
Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. San Francisco, CA.
Silva, Y. N., Aref,W. G., and Ali, M. H. (2009a). Similarity group-by. In Int’l Conf. Data Engineering (ICDE), pages 904–915. IEEE. DOI: 10.1109/ICDE.2009.113.
Silva, Y. N., Arshad, M. U., and Aref, W. G. (2009b). Exploiting similarity-aware grouping in decision support systems. In Int’l Conf. Extending Database Technology (EDBT), volume 360, pages 1144–1147. ACM. DOI: 10.1145/1516360.1516499.
Silva, Y. N., Sandoval, M., Prado, D., Wallace, X., and Rong, C. (2019). Similarity grouping in big data systems. In Intl Conf. Similarity Search and Applications (SISAP), volume 11807 of LNCS, pages 212–220. Springer. DOI: 10.1007/978-3-030-32047-8_19.
Stonebraker, M. and Pavlo, A. (2024). What goes around comes around... and around... SIGMOD Rec., 53(2):21–37.
Tang, M., Tahboub, R. Y., Aref, W. G., Atallah, M. J., Malluhi, Q. M., Ouzzani, M., and Silva, Y. N. (2016). Similarity group-by operators for multidimensional relational data. IEEE Trans. Knowl. Data Eng., 28(2):510–523. DOI: 10.1109/TKDE.2015.2480400.
Publicado
14/10/2024
Como Citar
MENDONÇA, Antônio Lívio C. de; BARIONI, Maria Camila N.; RAZENTE, Humberto.
Consultas analíticas por similaridade em SGBD Relacionais. In: BRAZILIAN E-SCIENCE WORKSHOP (BRESCI), 18. , 2024, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 48-55.
ISSN 2763-8774.
DOI: https://doi.org/10.5753/bresci.2024.243330.
