ML Anthology

Improving Compressed Counting

Ping Li
UAI 2009 pp. 329-338
/uai/2009/li2009uai-improving/

Abstract

Compressed Counting (CC) [22] was recently proposed for estimating the ath frequency moments of data streams, where 0 1. Monitoring Shannon entropy for anomaly detection (e.g., DDoS attacks) in large networks is an important task. This paper presents a new algorithm for improving CC. The improvement is most substantial when a -> 1--. For example, when a = 0:99, the new algorithm reduces the estimation variance roughly by 100-fold. This new algorithm would make CC considerably more practical for estimating Shannon entropy. Furthermore, the new algorithm is statistically optimal when a = 0.5.

UAI Semantic Scholar

Cite

Text

Li. "Improving Compressed Counting." Conference on Uncertainty in Artificial Intelligence, 2009.

Markdown

[Li. "Improving Compressed Counting." Conference on Uncertainty in Artificial Intelligence, 2009.](https://mlanthology.org/uai/2009/li2009uai-improving/)

BibTeX

@inproceedings{li2009uai-improving,
  title     = {{Improving Compressed Counting}},
  author    = {Li, Ping},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year      = {2009},
  pages     = {329-338},
  url       = {https://mlanthology.org/uai/2009/li2009uai-improving/}
}