Kaster, Daniel dos Santos [Orientador]Shimomura, Larissa Capobianco2024-05-012024-05-012019.00https://repositorio.uel.br/handle/123456789/11178Resumo: O desenvolvimento tecnológico acelerou o crescimento do volume de dados complexos como imagens, vídeos, séries temporais e dados geográficos Uma abordagem bastante utilizada para a recuperação de dados complexos são as consultas por similaridade As consultas por similaridade têm como objetivo principal recuperar dados similares a partir de características intrínsecas dos dados Assim, para facilitar a recuperação de dados complexos usando consultas por similaridade é necessário organizar grande quantidade de dados de forma que dados similares possam ser recuperados da forma mais rápida possível Diversos métodos de acesso foram propostos na literatura para tornar a recuperação por similaridade de grandes bases de dados mais rápida Artigos publicados recentemente indicam que métodos que utilizam grafos são bastante eficientes e superam o desempenho de métodos de outras categorias em várias situações Porém, de acordo com nosso conhecimento, nenhum trabalho se dedicou a realizar uma análise experimental em um número abrangente de métodos baseados em grafos utilizando os mesmos algoritmos de busca e o mesmo ambiente Esta Dissertação apresenta uma revisão bibliográfica sobre os principais tipos de grafos utilizados para consultas por similaridade, também foi realizado uma avaliação experimental utilizando os mesmos algoritmos de consulta com resposta exata e com resposta aproximada O métodos foram avaliados conforme seu comportamento considerando os principais parâmetros de construção e consulta para uma variedade de bases de dados reais A partir dos resultados desta avaliação foi proposto o método baseado em grafos, HGraph O HGraph é um método baseado em partições conectadas proposto para construir grafos de proximidade e responder consultas por similaridade O HGraph utiliza uma estratégia de divisão e conquista para construir tipos de grafos propostos na literatura Para conectar as diferentes partições do processo de divisão e conquista arestas longas foram adicionadas ao HGraph Foi avaliado o comportamento dos principais parâmetros do HGraph e seu desempenho quanto a tempo de construção e consultas por similaridade foram comparados com os métodos k-NNG (k-Nearest Neighbors Graph) , NSW (Navigable Small World Graph) e SAT (Spatial Approximation Tree) Como resultado, o HGraph foi capaz de melhorar o k-NNG em termos de tempo de construção, tempo de consulta e qualidade de resposta Além disso, o HGraph obteve melhor desempenho na busca em alguns datasets quando comparado ao NSW e a SATTeoria dos grafosProcessamento de dadosEspaços métricosRecuperação de dados (Computação)Graph theoryMetric spacesData processingDissertação