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 Ver menos

Abstract: In multimedia databases its common to represent objects using feature vectors, which are mapped onto a multidimensional space. In this thesis, the objects are image, and their feature vectors are obtained from their color histogram. The feature vectors mapping into a multidimensional space allows the utilization of spatial access structures, in order to efficiently perform similarity queries In this research multidimensional indexing structures are evaluated, from traditional spatial structures, R-tree and R*-tree, up to structures specially designed for high-dimen­sional spaces, like the SS-tree and SR-tree. Indeed, this work focus on the issue of the high-dimensionality of the feature space. Along with these structures, the M-tree, that indexes feature vectors in a non-dimensional manner, i.e., using the metric space, is also evaluated. To complete the evaluation, all the above structures are evaluated against the linear scan, in order to confirm the efficiency of the structures. To assure a homogeneous evaluation environment, the GiST framework was used to implement the structures, and the evaluation was performed using a data set of 40,000 feature vectors. A wide set of parameters was used evaluate construction and query processmg. The results obtained, indicate the SR-tree as the best structure for the real dataset. The M-tree was shown able to obtain good results, depending primarily upon the split technique used. This thesis also proposes new split techniques, and one of them was more resilient with respect to the increase in the number of dimensions. In addition, it is also shown that using the number of accessed pages as the only performance indicator may lead to wrong conclusions Ver menos