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

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

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.

Referências

Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426.

Broder, A. Z. (1997). On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21–29. IEEE.

Kannan, S., Naor, M., and Rudich, S. (1992). Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596–603.

Li, P. and König, A. C. (2010). b-bit minwise hashing. In Nineteenth International World Wide Web Conference (WWW 2010). Association for Computing Machinery, Inc.

Muller, J. H. (1988). Local structure in graph classes. PhD thesis, Georgia Institute of Technology.

Spinrad, J. P. (2003). Efficient graph representations. American mathematical society.