Practical aspects of ℓ₀-sampling algorithms
Resumo
The ℓ₀-sampling problem plays an important role in streaming graph algorithms. In this paper, we revisit a near-optimal ℓ₀-sampling algorithm, proposing a variant that allows proving a tighter upper bound for the probability of failure. We compare experimental results of both variants, providing empirical evidence of their applicability in real-case scenarios.
Referências
Ahn, K. J., Guha, S., and McGregor, A. (2012). Analyzing graph structure via linear measurements. In Proceedings of SODA’12, pages 459–467.
Cormode, G. and Firmani, D. (2014). A unifying framework for l0-sampling algorithms. Distributed and Parallel Databases, 32(3):315–335.
Cormode, G., Muthukrishnan, S., and Rozenbaum, I. (2005). Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In Proceedings of VLDB’05, pages 25–36.
Jowhari, H., Sağlam, M., and Tardos, G. (2011). Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of PODS’11, pages 49–58.
McGregor, A. (2014). Graph stream algorithms: a survey. ACM SIGMOD Record, 43(1):9–20.
Monemizadeh, M. and Woodruff, D. P. (2010). 1-pass relative-error lp-sampling with applications. In Proceedings of SODA’10, pages 1143–1160.
Cormode, G. and Firmani, D. (2014). A unifying framework for l0-sampling algorithms. Distributed and Parallel Databases, 32(3):315–335.
Cormode, G., Muthukrishnan, S., and Rozenbaum, I. (2005). Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In Proceedings of VLDB’05, pages 25–36.
Jowhari, H., Sağlam, M., and Tardos, G. (2011). Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of PODS’11, pages 49–58.
McGregor, A. (2014). Graph stream algorithms: a survey. ACM SIGMOD Record, 43(1):9–20.
Monemizadeh, M. and Woodruff, D. P. (2010). 1-pass relative-error lp-sampling with applications. In Proceedings of SODA’10, pages 1143–1160.
Publicado
26/07/2018
Como Citar
LOPES, Juan P. A.; OLIVEIRA, Fabiano S.; BARBOSA, Valmir C..
Practical aspects of ℓ₀-sampling algorithms. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 33-36.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3145.
