Avaliação de desempenho de estruturas de acesso a dados hiperdimensionais

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

Em bancos de dados multimídia é comum a representação de objetos utilizando vetores de características, que são, por sua vez, mapeados em um espaço multidimensional. Nesta dissertação, os objetos utilizados são imagens, e os vetores de características são obtidos através dos seus histogramas de cores. O mapeamento dos vetores de características em um espaço multidimensional permite a utilização de estruturas de indexação espaciais, proporcionando a realização de consultas de similaridade de forma eficiente. Este trabalho são avaliadas algumas estruturas de indexação para dados multidimen­sionais, que vão de estruturas espaciais tradicionais, como a R-tree e a R* -tree, a estrutu­ras espaciais adaptadas para espaços hiperdimensionais, como a SS-tree e a SR-tree. De fato, este trabalho se concentra no aspecto da alta dimensionalidade dos vetores de ca­racterísticas. Paralelo a estas estruturas, a M-tree, que realiza a indexação dos vetores de características de forma adimensional, i.e., no espaço métrico, é também avaliada. Para completar a avaliação, é feita a comparação dessa estruturas em relação a busca linear, a fim de confirmar a eficiência das estruturas avaliadas. Para assegurar um ambiente de avaliação homogêneo, foi utilizado o ambiente de programação GiST para a implementação das estruturas, e, nas avaliações das estruturas, foi utilizado um conjunto de dados reais de 40.000 elementos. Um conjunto bastante amplo de parâmetros de construção e consulta dos índices permitiu a avaliação das estruturas. Nos resultados obtidos, a SR-tree se mostrou a melhor estrutura com os conjuntos de dados reais. A M-tree mostrou poder alcançar bons resultados, dependendo da técnica de split utilizada. Nesta dissertação são propostas novas técnicas de split sendo uma delas mais robusta em relação ao aumento do número de dimensões. Além desses resultados, é mostrado que o uso de número de páginas acessadas como único indicador de desempenho pode levar a conclusões incorretas

ASSUNTO(S)

indexação sistemas multimidia estruturas de dados (computação) banco de dados

ACESSO AO ARTIGO

Documentos Relacionados