A+A-ContrastAcessibilidade
EnglishPortuguese
Buscar

Defesa de Doutorado de Javier Alvaro Vargas Muñoz

12 Mar
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