Representações Implícitas Probabilísticas de Grafos

• Juan P. A. Lopes
• Fabiano de S. Oliveira
• Paulo E. D. Pinto

DOI: https://doi.org/10.5753/etc.2017.3179

Resumo

This paper introduces the concept of probabilistic implicit graph representations, extending the definition from [Spinrad 2003] by allowing the adjacency test to have a constant probability of false positives or false negatives. It also discusses two novel representations based on well-known probabilistic data structures: one that uses Bloom filters and can represent general graphs with the same space complexity as the adjacency matrix (but outperforms it for sparse graphs), and other that uses MinHash and can represent trees with lower space complexity than any deterministic implicit representation.