Estruturas de Dados Probabilísticas Aplicadas à Representação Implícita de Grafos
| Ano de defesa: | 2017 |
|---|---|
| Autor(a) principal: | |
| Orientador(a): | |
| Banca de defesa: | |
| Tipo de documento: | Dissertação |
| Tipo de acesso: | Acesso aberto |
| Idioma: | por |
| Instituição de defesa: |
Universidade do Estado do Rio de Janeiro
Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística BR UERJ Programa de Pós-Graduação em Ciências Computacionais |
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: | |
| Link de acesso: | http://www.bdtd.uerj.br/handle/1/7720 |
Resumo: | Esta dissertação apresenta duas principais contribuições. É feito um resumo da literatura sobre quatro estruturas de dados probabilísticas importantes: Bloom filters, CountMin 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 |