| Compartilhamento |
|
Exportar este item:
Use este identificador para citar ou linkar para este item:
http://www.bdtd.uerj.br/handle/1/7720| Tipo do documento: | Dissertação |
| Título: | Estruturas de Dados Probabilísticas Aplicadas à Representação Implícita de Grafos |
| Título(s) alternativo(s): | Probabilistic data structures applied to implicit graph representation |
| Autor: | Lopes, Juan Pedro Alves  |
| Primeiro orientador: | Pinto, Paulo Eustáquio Duarte |
| Primeiro coorientador: | Oliveira, Fabiano de Souza |
| Primeiro membro da banca: | Szwarcfiter, Jayme Luiz |
| Segundo membro da banca: | Coelho, Igor Machado |
| Terceiro membro da banca: | Barbosa, Valmir Carneiro |
| 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 |
| Abstract: | This thesis comprises two major contributions. It summarizes the literature about four important probabilistic data structures: Bloom filters, Count-Min sketch, MinHash, and HyperLogLog, discussing their definition, variants, error bounds, and practical applications, while providing new experimental data about them. Also, it discusses the application of probabilistic data structures to the graph representation problem. Two new probabilistic representations are introduced here: one that uses Bloom filters and can represent general graphs with the same complexity as the adjacency matrix (but outperforms it for sparse graphs), the other that uses MinHash and can represent trees with lower complexity than the optimal deterministic implicit representation |
| Palavras-chave: | Probabilistic data structures graphs graph representation Estruturas de dados probabilísticas grafos representação de grafos Grafos Teoria |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Instituição: | Universidade do Estado do Rio de Janeiro |
| Sigla da instituição: | UERJ |
| Departamento: | Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística |
| Programa: | Programa de Pós-Graduação em Ciências Computacionais |
| Citação: | LOPES, Juan Pedro Alves. Estruturas de Dados Probabilísticas Aplicadas à Representação Implícita de Grafos. 2017. 104 f. Dissertação (Mestrado em Modelagem matemático-estatístico-computacional) - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2017. |
| Tipo de acesso: | Acesso Aberto |
| URI: | http://www.bdtd.uerj.br/handle/1/7720 |
| Data de defesa: | 10-Mar-2017 |
| Aparece nas coleções: | Mestrado em Ciências Computacionais |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| merged.pdf | 1,88 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.