Seminário Ence: Hashing sensível à localidade (LSH, Locality-Sensitive Hashing) para busca de vizinho mais próximo em espaços métricos.

 Escola Nacional de Ciências Estatísticas

Seminário Ence

A Ence tem o prazer de convidar para a palestra:

Hashing sensível à localidade (LSH, Locality-Sensitive Hashing) para busca de vizinho mais próximo em espaços métricos.

Palestrante

Eliezer de Souza da Silva

Instituto Brasileiro de Geografia e Estatística – IBGE/Diretoria de Informática - DI

Dia: 08/12/2014 – segunda-feira

Horário: 16h00-18h00

Local: Ence – Rua André Cavalcanti, 106 - sala 306 – Bairro de Fátima

Resumo: A crescente disponibilidade de conteúdo multimídia é um desafio para a pesquisa em Recuperação de Informação. Usuários querem não apenas ter acesso aos documentos multimídia, mas também obter semântica destes documentos, de modo que a capacidade de encontrar um conteúdo específico em grandes coleções de documentos textuais e não textuais é fundamental. Nessas grandes escalas, sistemas de informação multimídia de recuperação devem contar com a capacidade de executar a busca por semelhança de forma eficiente. No entanto, documentos multimídia são muitas vezes representados por descritores multimídia representados por vetores de alta dimensionalidade, ou por outras representações complexasem espaços métricos. Fornecer a possibilidade de uma busca por similaridade eficiente para esse tipo de dados é extremamente desafiador. Neste trabalho, exploramos uma das famílias mais mais citado de soluções para a busca de similaridade, o Hashing Sensível à Localidade (LSH - Locality-sensitive Hashing em inglês), que se baseia na criação de funções de hash que atribuem, com maior probabilidade, a mesma chave para os dados que são semelhantes. Propomos dois métodos novos para o LSH, generalizando-o para espaços métricos quaisquer utilizando particionamento métrico (centróides aleatórios e k-medoids). Apresentamos uma comparação com os métodos LSH bem estabelecidos em espaços vetoriais e com os últimos novos métodos concorrentes para espaços métricos. Desenvolvemos uma modelagem teórica do comportamento probalístico dos algoritmos propostos e demonstramos algumas relações e limitantes para a probabilidade de colisão de hash. Dentre os algoritmos propostos para generelizar LSH para espaços métricos, esse desenvolvimento teórico é novo. Nossa apresentação trará uma discussão inicial sobre algoritmos e estruturas de dados probabilísticas e suas aplicações em contexto de alta escala (buzzword Big Data), contextualizando para o problema específico de busca de similaridade em espaços métricos e nossas contribuições.

A participação é aberta e contamos com a participação de todos os professores e alunos da pós-graduação, da especialização e da graduação, assim como de todos os funcionários do IBGE.

Informações: Tel.: 2142-4696 - 2142-4691

e-mail: O endereço de e-mail address está sendo protegido de spambots. Você precisa ativar o JavaScript enabled para vê-lo.

Coordenações da Graduação e da Pós-Graduação