Parametrização da estrutura de dados métrica RLC

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Em muitas aplicações, existe a necessidade de pesquisar objectos semelhantes ou próximos de um objecto dado. Exemplos desses objectos incluem imagens médicas ou de rostos, sequências de proteínas ou de ADN, palavras de uma língua ou trajectórias de furacões. As pesquisas por proximidade podem ser formalizadas no contexto de espaços métricos, onde a semelhança entre dois elementos do domínio é medida através da função de distância. Como, em geral, as bases de dados possuem muitos elementos e o cálculo da distância entre dois objectos é uma operação cara, foram desenvolvidas estruturas de dados que tentam minimizar o número de distâncias calculadas durante as pesquisas deste tipo, designadas por estruturas de dados métricas. Nesta tese, faz-se um levantamento dos espaços métricos mais frequentemente usados nos testes de desempenho das estruturas de dados métricas. Depois, descreve-se a evolução da estrutura de dados métrica Recursive Lists of Clusters (RLC), caracterizando-se as suas variantes. O desempenho da RLC, tal como o de qualquer estrutura de dados métrica parametrizada, depende fortemente dos valores dos seus parâmetros. O problema é que os valores mais adequados a cada espaço métrico têm sido encontrados por observação de resultados experimentais, tornando o processo de parametrização pouco fiável e muito moroso. Para atacar esta questão, propõe-se uma nova variante da RLC cujos valores dos parâmetros dependem de valores extraídos do espaço métrico. Os resultados experimentais, que envolvem quinze espaços métricos de diferentes domínios, mostram que a nova variante é mais eficiente do que a anterior.