Estruturas de Dados Probabilísticas para Representação de Conjuntos
Resumo
Este artigo descreve os aspectos mais importantes das estruturas de dados probabilísticas Filtro de Bloom, Count-Min Sketch, MinHash e Hyper-LogLog, que permitem, através do uso de funções de hash, estimar algumas propriedades sobre conjuntos e multiconjuntos sem a necessidade de mantê-los em memória. Todas as estruturas apresentadas neste artigo são construídas através de algoritmos online facilmente paralelizáveis, o que as torna especialmente importantes no cenário de grandes volumes de dados onde uma resposta aproximada é aceitável.
Referências
Babcock, B., Babu, S., Datar, M., Motwani, R., andWidom, J. (2002). Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1–16. ACM.
Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426.
Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., and Varghese, G. (2006). An improved construction for counting bloom filters. In Algorithms–ESA 2006, pages 684–695. Springer.
Broder, A. Z. (1997). On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21–29. IEEE.
Cormode, G. and Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75.
Flajolet, P. and Martin, G. N. (1985). Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182–209.
Gibbons, P. B. and Matias, Y. (1999). Synopsis data structures for massive data sets. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 909–910. Society for Industrial and Applied Mathematics.
Real, R. and Vargas, J. M. (1996). The probabilistic basis of jaccard’s index of similarity. Systematic biology, pages 380–385.
Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426.
Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., and Varghese, G. (2006). An improved construction for counting bloom filters. In Algorithms–ESA 2006, pages 684–695. Springer.
Broder, A. Z. (1997). On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21–29. IEEE.
Cormode, G. and Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75.
Flajolet, P. and Martin, G. N. (1985). Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182–209.
Gibbons, P. B. and Matias, Y. (1999). Synopsis data structures for massive data sets. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 909–910. Society for Industrial and Applied Mathematics.
Real, R. and Vargas, J. M. (1996). The probabilistic basis of jaccard’s index of similarity. Systematic biology, pages 380–385.
Publicado
04/07/2016
Como Citar
LOPES, Juan P. A.; PINTO, Paulo E. D.; OLIVEIRA, Fabiano de S..
Estruturas de Dados Probabilísticas para Representação de Conjuntos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 899-902.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9855.
