12 mar 2020
09:00 Defesa de Doutorado Sala 85 - IC 2
Tema
Large Scale Indexing of High Dimensional Data via Nearest Neighbors Graphs
Aluno
Javier Alvaro Vargas Muñoz
Orientador / Docente
Ricardo da Silva Torres
Breve resumo
Uma principal rotina 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.e., textos, imagens, vídeos), é a Busca dos Vizinhos Mais Próximos. Esse problema consiste 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 artesanais, como o objetivo de facilitar o processamento desses objetos. Na última década, muitos de essas coleções de dados altamente dimensionais tem crescido massivamente com o uso extensivo das mídias sociais, rapidamente alcançando a escala de milhões 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.e., 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. As principais contribuições apresentadas em essa 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últiplas clusterizações hierárquicas; (ii) a introdução de novas heurísticas que usam clássicas KD-Trees para melhorar os resultados das buscas por meio de uma melhor seleção do vértice inicial e guiando o atravesamento 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 verdadeiros vizinhos mais próximos; (iv) a primeira técnica baseada em grafos de vizinhos mais próximos que suporta buscas eficientes em coleções com bilhões de dados, usando um consumo razoável de recursos computacionais.
Banca examinadora
Titulares:
| Ricardo da Silva Torres | IC/UNICAMP |
| José Fernando Rodrigues Júnior | ICMC/USP |
| Altigran Soares da Silva | IComp/UFAM |
| Esther Luna Colombini | IC/UNICAMP |
| Hélio Pedrini | IC/UNICAMP |
Suplentes:
| Alexandre Mello Ferreira | IC/UNICAMP |
| Marcos Vinicius Mussel Cirne | IC/UNICAMP |
| Edleno Silva de Moura | IComp/UFAM |