Estruturas de dados métricas genéricas em memória secundária

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

À medida que a complexidade dos tipos de dados modernos foi crescendo, os espaços métricos tornaram-se num paradigma popular para pesquisas por similaridade. Devido aos formatos complexos dos dados (e.g. vídeos, imagens ou sons) e também à elevada quantidade de informação, é crucial poupar tempo neste tipo de pesquisas, evitando que se analisem todos os objectos da base de dados cada vez que uma procura é efectuada. O tempo dispendido está directamente relacionado com o número de cálculos de distância entre dois objectos e com o número de acessos a disco. Sendo assim, o principal objectivo de qualquer estrutura de dados métrica implementada em memória secundária é minimizar essas duas quantidades. Neste trabalho é apresentada a Recursive Lists of Clusters 2 (RLC2), uma estrutura de dados métrica genérica, dinâmica e implementada em memória secundária. Esta estrutura é uma variante de outra estrutura de dados, a Recursive Lists of Clusters (RLC) [Mam07]. Adicionalmente, estudam-se várias estruturas de dados inseridas no mesmo âmbito que a RLC2 e apresentam-se os resultados de uma bateria de testes que comparam os seus desempenhos. Nos testes efectuados, a RLC2 revelou-se muito eficiente nas pesquisas por proximidade e muito competitiva nas inserções de objectos.