logo_uerj.gif (2426 bytes)

UERJ/IME/CC-COMP
Tese de Mestrado: Estruturas de Dados Probabilísticas Aplicadas à Representação Implícita de Grafos (pdf)
Autor: Juan Pedro alves Lopes
Orientadores: Fabiano de Souza Oliveira
                         Paulo Eustáquio Duarte Pinto


Resumo:

Esta dissertação apresenta duas principais contribuições. É feito um resumo da literatura sobre quatro estruturas de dados probabilísticas importantes: Bloom filters, Count-Min sketch, MinHash e HyperLogLog. São discutidas suas definições, variantes, limites de erro e aplicações práticas. Novos dados experimentais sobre essas estruturas foram produzidos para este trabalho. Além disso, é discutida aqui a aplicação de estruturas de dados probabilísticas para o problema de representação de grafos. Duas novas representações probabilísticas são introduzidas aqui: uma que usa filtros de Bloom e pode representar grafos gerais com a mesma complexidade da matriz de adjacência (sendo até melhor para grafos esparsos), e outra que usa MinHash e pode representar árvores com complexidade menor que a representação determinística ótima.

Programas de apoio:

Última atualização: 25/02/2018


home
Home

topo
Topo