Desenvolvimento de algoritmos genéticos para consultas por similaridade em domínios métricos

Autor(es)

Renato Bueno

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2005-05-30

Membros da banca

Caetano Traina Junior; Karin Becker; André Carlos Ponce de Leon Ferreira de Carvalho

• Orientador: Caetano Traina Junior

Resumo

O custo do acesso exato a dados complexos tende a ser muito alto, do ponto de vista da carga de processamento computacional. Além disso, a operação de busca em dados multimídia não é efetuada realmente sobre os dados originais, mas sobre características extraídas desses dados, as quais os descrevem. Por exemplo, na busca por imagens similares utilizando-se histogramas de cor, realizando uma consulta exata, o que se obtém são as imagens cujos histogramas são exatamente os mais similares aos da imagem referenciada 11a consulta, mas isso não implica necessariamente que se obtenha as imagens que atendam exatamente a consulta efetuada, pois as imagens recuperadas podem ser muito diferentes quanto a forma, por exemplo. Portanto, em muitas aplicações que acessam dados complexos, a recuperação exata deixa de um requisito fundamental, podendo a exatidão das respostas ser trocada por um melhor desempenho Neste trabalho foram desenvolvidos algoritmos para recuperação aproximada do conjunto-resposta de consultas por similaridade em domínios métricos utilizando algoritmos genéticos. Neste trabalho, com a utilização de algoritmos genéticos, foram desenvolvidas técnicas de recuperação aproximada de dados cm domínio métrico, cujo refinamento das respostas obtidas é dependente do tempo de processamento disponível, definido pelo usuário. Os algoritmos desenvolvidos foram implementados utilizando a Slim-tree, mas outros métodos de acesso podem ser extendidos para utilizá-los também. Os algoritmos contemplam consultas por abrangência e vizinhos mais próximos, além de algumas variações. Os algoritmos desenvolvidos foram testados e validados com conjuntos de dados sintéticos e reais, e mostraram-se capazes de obter respostas aproximadas com boa precisão utilizando apenas uma fração do tempo exigido pela consulta exata. Os resultados obtidos nos experimentos mostram que é possível obter respostas com precisão superior a 90% utilizando apenas metade do tempo da consulta exata com o algoritmo convencional, e até 65% de precisão com apenas um quinto do tempo da consulta exata. (AU)

• Processo FAPESP: 02/11771-3 - Desenvolvimento de algoritmos geneticos para consultas por similaridade em dominios metricos.
• Beneficiário: Renato Bueno
• Modalidade de apoio: Bolsas no Brasil - Mestrado