Efficient Indexing of Multiple Metric Spaces for Similarity Query Optimization

Com o crescente aumento na geração de dados ao longo dos últimos anos, tornou-se necessário a captura e armazenamento de grandes quantidades de dados complexos, como imagens, vídeos e áudios, que exigem ferramentas eficientes e flexíveis quando utilizados na recuperação de informações. Muitas abordagens da literatura para recuperar dados complexos seguem o paradigma de Consultas por similaridade, utilizando Métodos de Acesso Métrico (MAMs) para indexar os dados complexos e acelerar a recuperação de informações. Estes métodos indexam vetores de características, extraídos por meio da aplicação de Métodos de Extração de Características (FEMs), que representam o conteúdo intrínseco existente nos dados complexos, como cor, textura ou forma no caso de imagens. Os MAMs foram inicialmente projetados para indexar recursos de dados complexos usando apenas um FEM por vez, levando os usuários a criar vários índices quando mais de um FEM é utilizado nas consultas. Abordagens recentes que utilizam diferentes representações em uma única estrutura de índice, no geral sofrem com um grande número de cálculos de distância, causado principalmente pelo aumento no número de elementos candidatos gerados na recuperação de informações sobre os multiplos espaços métricos. De forma a solucionar este problema, neste trabalho de mestrado, propomos o MAM Spectra, que indexa dados complexos usando vários FEMs simultaneamente, e tem como objetivo principal, agilizar as consultas por similaridade sobre múltiplas representações de objetos complexos. Além disso, o MAM se baseia nas correlações existentes entre diferentes espaços para escolher os melhores FEMs para responder a cada busca, de forma a obter um espaço de indexação que reduza o número de cálculos de distância e consequentemente o tempo de execução de consultas. Nossos resultados utilizando o Spectra mostram que, para diferentes conjuntos de dados, os espaços métricos que apresentam baixa-correlação, resultam em uma redução significativa do número de elementos presentes no conjunto de elementos candidatos, enquanto preserva a qualidade da busca e reduz o tempo de consulta em até uma ordem de magnitude.With the increase in data generation over the past few years, it has become necessary to capture and store large amounts of complex data, such as images, videos and audios, which require efficient and flexible tools for information retrieval. Many existing approaches in the literature to recover complex data follow the Similarity Queries paradigm, using Metric Access Methods (MAMs) to index complex data and speed up the queries. These methods are usually employed to index feature vectors, extracted by Feature Extraction Methods (FEMs), which represent the intrinsic content of the complex data, such as color, texture or shape in the case of images. The MAMs were initially designed to index complex datasets using just one FEM, leading users to create multiple indexes when more than one FEM were needed. Recent approaches that use different representations in a single index structure generally suffer from a large number of distance calculations caused mainly by the increase in the number of candidate elements generated in the information retrieval over various metric spaces. To solve this problem, in this work, we propose the Spectra MAM, which is able to index complex data using several FEMs simultaneously, and its main objective is to speed up the execution of queries by similarity in various representations of complex objects. In addition, Spectra relies on the correlations existing between different spaces to choose the best FEMs, in order to obtain an indexing space that allows reducing the number of distance calculations, and consequently the query execution time. Our results using the Spectra show that, for different data sets, the metric spaces that have low correlation result in a significant reduction in the number of elements present in the set of candidate elements, preserving the quality of the search and reducing the execution time of queries by up to an order of magnitude