Resumo: Uma tarefa comum em muitas tarefas relacionadas às áreas de Recuperação de Informa-ção, Visão Computacional e Aprendizado de Máquina, que envolvem objetos multimídia (p.ex., textos, imagens, vídeos), é a Busca dos Vizinhos Mais Próximos. Essa tarefa con-siste em retornar o subconjunto de objetos de uma coleção que são mais similares a um objeto de consulta. Objetos multimídia são comummente mapeados para representações vetoriais altamente dimensionais utilizando técnicas guiadas pelos dados ou soluções ar-tesanais, com o objetivo de facilitar o processamento desses objetos. Na última década, muitas dessas coleções de dados altamente dimensionais têm crescido massivamente com o uso extensivo das mídias sociais, rapidamente alcançando a escala de milhões de itens de dados, e, em alguns casos, bilhões. Isso tem motivado muitos esforços dedicados ao desenvolvimento de estruturas de dados para dar suporte a buscas eficientes dos vizinhos mais próximos em grandes coleções de dados. Recentemente a criação de Grafos de Vizinhos mais Próximos tem ganhado muita atenção já que essa abordagem tem demonstrado um desempenho consistentemente melhor que as abordagens clássicas: Árvores de Particionamento do Espaço (p.ex., KD-Trees) e Hashing. A ideia principal é criar um grafo onde cada vértice corresponde a um único objeto da coleção, e cada um deles está conectado com os outros mais similares na coleção. Motivados pelo sucesso desse grupo de técnicas em recentes benchmarks, quando avaliados em coleções de milhões de itens de dados, nós focamos esta tese em pesquisar novas abordagens para a criação de grafos de vizinhos mais próximos e algoritmos para realizar buscas nessas estruturas, com o objetivo de dar suporte a buscas mais eficientes e precisas. Além disso, como a maioria das técnicas existentes para busca de vizinhos mais próximos, incluindo as baseadas em grafos, não são capazes de escalar até coleções com bilhões de itens de dados, principalmente devido aproblemas relacionados à memória, nós também investigamos técnicas para compressão de representações vetoriais e estratégias de poda para criação de grafos muito esparsos. As principais contribuições apresentadas nesta tese são: (i) o desenvolvimento de uma nova abordagem para criar eficientemente grafos esparsos de vizinhos mais próximos, baseado no resultado de múltiplos agrupamentos hierárquicos; (ii) a introdução de novas heurísticas que usam KD-Trees para melhorar os resultados das buscas por meio de uma melhor seleção do vértice inicial e guiando a navegação do grafo; (iii) um novo arcabouço supervisionado para conduzir a navegação em grafos de vizinhos mais próximos baseada na informação topológica dos vértices, reduzindo o número de vértices explorados para encontrar os vizinhos mais próximos verdadeiros; (iv) a primeira técnica baseada em grafos de vizinhos mais próximos que suporta buscas eficientes em coleções com bilhões de itens de dados, usando uma quantidade razoável de recursos computacionais. Os experimentos realizados para validar nossas propostas evidenciaram ganhos consistentes em relação às abordagens clássicas e resultados competitivos com o estado da arte em cenários com milhões e bilhões de itens de dados Ver menos

Abstract: A principal routine in many Information Retrieval, Computer Vision, and Machine Learning tasks involving multimedia objects (e.g., text, image, video) is the Nearest Neighbor (NN) search. This problem consists in returning a subset of objects from a collection that is more similar to a query object. Multimedia objects are commonly mapped to a high dimensional vector representations employing hand-crafted or data-driven descriptors aiming to facilitate their processing. In the last decade, many of these collections of high dimensional data have grown massively with the extensive use of social media, quickly reaching the scale of millions and, in some cases, billions. This has motivated a lot of efforts dedicated in the development of data structures to support efficient NN searches on large collections. Recently, the creation of Nearest Neighbor Graphs has gained a lot of attention since they have demonstrated to perform consistently better than classical approaches, e.g., Space Partitioning Trees (e.g., KD-Trees) and Hashing. The idea is to create a graph where each vertex corresponds to a unique collection's object, and each of them is connected with the other similar ones. Motivated by the success of these groups of techniques in recent benchmarks, when evaluated on million-size datasets, we focus on this thesis to investigate novel approaches to creation of nearest neighbor graphs and algorithms to perform search over them, aiming to support more efficient and accurate NN searches. Furthermore, since most of existing techniques for NN search, including state-of-the-art graph-based approaches, are not able to scale up-to billion-size datasets, this principally caused by memory related issues, we also investigate compression techniques for vector representations and pruning strategies for creation of very sparse graphs. The principal contributions presented in this thesis are: (i) the development of a novel approach to create efficiently sparse nearest neighbors graphs, based on the results of multiple hierarchical clustering executions; (ii) the introduction of novel heuristics that employ classical KD-Trees to improve graph search results by better selecting the initial vertex and guiding the graph traversal; (iii) a novel learning framework that conduces the navigation on nearest neighbor graphs based on the topological information of vertices, reducing the number of vertices explored to reach the true nearest neighbors; (iv) the first nearest neighbor graph-based technique that supports nearest neighbor searches on billion-size datasets, using a reasonable resource consumption. The experiments conduced to validate our proposals evidenced consistent gains over classic approaches and competitive results with state of the art in both million and billion scale scenarios Ver menos