Practical aspects of ℓ₀-sampling algorithms
Abstract
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.
References
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.
Published
2018-07-26
How to Cite
LOPES, Juan P. A.; OLIVEIRA, Fabiano S.; BARBOSA, Valmir C..
Practical aspects of ℓ₀-sampling algorithms. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
