A Very Efficient Scheme for Estimating Entropy of Data Streams Using Compressed Counting
| dc.creator | Li, Ping | |
| dc.date | 2008-08-13 | |
| dc.date | 2008-08-21 | |
| dc.date.accessioned | 2026-07-07T09:57:27Z | |
| dc.date.available | 2026-07-07T09:57:27Z | |
| dc.description | Compressed Counting (CC)} was recently proposed for approximating the $α$th frequency moments of data streams, for $0<α\leq 2$. Under the relaxed strict-Turnstile model, CC dramatically improves the standard algorithm based on symmetric stable random projections}, especially as $α\to 1$. A direct application of CC is to estimate the entropy, which is an important summary statistic in Web/network measurement and often serves a crucial "feature" for data mining. The Rényi entropy and the Tsallis entropy are functions of the $α$th frequency moments; and both approach the Shannon entropy as $α\to 1$. A recent theoretical work suggested using the $α$th frequency moment to approximate the Shannon entropy with $α=1+δ$ and very small $|δ|$ (e.g., $<10^{-4}$). In this study, we experiment using CC to estimate frequency moments, Rényi entropy, Tsallis entropy, and Shannon entropy, on real Web crawl data. We demonstrate the variance-bias trade-off in estimating Shannon entropy and provide practical recommendations. In particular, our experiments enable us to draw some important conclusions: (1) As $α\to 1$, CC dramatically improves {\em symmetric stable random projections} in estimating frequency moments, Rényi entropy, Tsallis entropy, and Shannon entropy. The improvements appear to approach "infinity." (2) Using {\em symmetric stable random projections} and $α= 1+δ$ with very small $|δ|$ does not provide a practical algorithm because the required sample size is enormous. | |
| dc.identifier | https://arxiv.org/abs/0808.1771 | |
| dc.identifier | http://arxiv.org/abs/0808.1771 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167347 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | A Very Efficient Scheme for Estimating Entropy of Data Streams Using Compressed Counting | |
| dc.type | text |