Streaming and sublinear approximation of entropy and information distances
From MaRDI portal
Publication:3581507
DOI10.1145/1109557.1109637zbMath1192.94075arXivcs/0508122OpenAlexW2949196898MaRDI QIDQ3581507
Sudipto Guha, Venkatasubramanian Suresh, Andrew McGregor
Publication date: 16 August 2010
Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0508122
Related Items
Big Data on the Rise? ⋮ Improved algorithms for distributed entropy monitoring ⋮ Optimal sampling from sliding windows ⋮ Testing shape restrictions of discrete distributions ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$ ⋮ Fast adaptive algorithms for abrupt change detection ⋮ Recovering Structured Probability Matrices ⋮ Sketching information divergences ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\)