Tese

Evaluating similarity in DBMSs: Towards query optimization (2024)

• Authors:
  • Eleutério, Igor Alberte Rodrigues
  • Traina Junior, Caetano (Orientador)
• Autor USP: ELEUTÉRIO, IGOR ALBERTE RODRIGUES - ICMC
• Unidade: ICMC
• Sigla do Departamento: SCC
• DOI: 10.11606/D.55.2024.tde-23072024-143549
• Subjects: BANCO DE DADOS RELACIONAIS; GERENCIADORES DE BANCO DE DADOS; DADOS CINÉTICOS
• Keywords: Consultas por similaridade; Gist R-tree; Gist R-tree; Métodos de Acesso Métricos; Metric access methods; Optimization; Otimização; Relational database management systems; Similarity queries
• Language: Inglês
• Abstract: Sistemas Gerenciadores de Banco de Dados Relacionais (SGBDRs) são sistemas onipresentes que armazenam e recuperam dados em diversos cenários. Eles são adequados para lidar com dados escalares, como números, strings curtas e datas, para os quais as relações de Identidade (=, ≠) e Ordem (≤, ≥, < , >) são úteis. No entanto, eles enfrentam dificuldades com dados complexos como imagens, vídeos e trilhas de áudio. Para este tipo de dado, as relações de Identidade e Ordem não são significativas. Nesse contexto, as Consultas por Similaridade são notáveis por serem uma abordagem para comparar e avaliar objetos complexos. Duas consultas de similaridade dignas de nota são Range e k-NN. Muitos trabalhos na literatura implementam sistemas para realizar consultas de similaridade. No entanto, eles possuem limitações, como não utilizar estruturas de SGBDR para permitir consultas tradicionais, não implementar índices ou exigir alterações nos comandos SQL para operar consultas de similaridade. Nesta dissertação de mestrado, implementamos dois sistemas: MIGUE-Sim e CoSIM-Gres, cada um com suas próprias contribuições para a literatura. O MIGUE-Sim está focado na implementação de consultas de similaridade usando apenas recursos nativos do Postgres. Com esse sistema, avaliamos diferentes maneiras de representar uma consulta k-NN em SQL puro, e nossa consulta proposta é até 10% mais rápida do que nosso principal concorrente. Além disso, usamos o índice Gist R-tree nativo para realizarconsultas k-NN, e ele atingiu uma aceleração de desempenho de até 96% em relação ao nosso concorrente. O CoSIM-Gres está focado na implementação de três métodos de acesso diferentes para realizar consultas de similaridade em SGBDR: Acesso Sequencial, MAM Slim-tree e Gist R-tree. Até onde sabemos, esta é a primeira discussão aprofundada sobre o desempenho de consultas de similaridade envolvendo diferentes métodos de acesso em SGBDR. Avaliamos diferentes cardinalidades, dimensionalidades e funções de distância, e nossos resultados apontam que: i) as funções de distância da família Minkowski não impactam significativamente o desempenho dos métodos de acesso; ii) Quando o número esperado de elementos recuperados é baixo em comparação com o número total de elementos na tabela (cerca de 5%), o MAM é muito melhor do que o Acesso Sequencial; iii) Quando o número esperado de elementos recuperados pela consulta é de até 50% do conjunto de dados, o MAM é melhor do que o Acesso Sequencial; caso contrário, é melhor realizar um Acesso Sequencial; iv) Quando a Gist R-tree está disponível, é melhor do que MAM Slim-tree e Acesso Sequencial para recuperar até 20% do conjunto de dados. Nossos resultados são relevantes para trabalhos futuros sobre otimização de consultas de similaridade em SGBDR.
• Imprenta:
  • Publisher place: São Carlos
  • Date published: 2024
• Data da defesa: 22.05.2024

Informações sobre o DOI: 10.11606/D.55.2024.tde-23072024-143549 (Fonte: oaDOI API)
• Este periódico é de acesso aberto
• Este artigo é de acesso aberto
• URL de acesso aberto
• Cor do Acesso Aberto: gold
• Licença: cc-by-nc-sa

---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  ELEUTÉRIO, Igor Alberte Rodrigues. Evaluating similarity in DBMSs: Towards query optimization. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23072024-143549/. Acesso em: 28 dez. 2025.

• APA

  Eleutério, I. A. R. (2024). Evaluating similarity in DBMSs: Towards query optimization (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23072024-143549/

• NLM

  Eleutério IAR. Evaluating similarity in DBMSs: Towards query optimization [Internet]. 2024 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23072024-143549/

• Vancouver

  Eleutério IAR. Evaluating similarity in DBMSs: Towards query optimization [Internet]. 2024 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23072024-143549/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• LLMs são bons matemáticos?: Avaliando o desempenho em resolução de exercícios
• A novel approach to reduce the financial and computational costs of similarity queries over document collections in NoSQL databases
• MIGUE-Sim: speeding up similarity queries with native RDBMS resources
• Similarity-slim extension: reducing financial and computational costs of similarity queries in document collections in NoSQL databases
• KluSIM: speeding up k-medoids clustering over dimensional data with metric access method
• MiDaS: extract golden results from knowledge discovery even over incomplete databases
• TraiRANN: evaluating data reduction methods for neural network training in medical applications
• Cosim-Gres: towards similarity queries optimization inside RDBMS