Estimating Entropy of Data Streams Using Compressed Counting

Details Estimating Entropy of Data Streams Using Compressed Counting Estimating Entropy of Data Streams Using Compressed Counting

2009-10-08

arxiv.org/abs/0910.1495v1

Computer Science

Data Structures and Algorithms

Scientific paper

The Shannon entropy is a widely used summary statistic, for example, network traffic measurement, anomaly detection, neural computations, spike trains, etc. This study focuses on estimating Shannon entropy of data streams. It is known that Shannon entropy can be approximated by Reenyi entropy or Tsallis entropy, which are both functions of the p-th frequency moments and approach Shannon entropy as p->1. Compressed Counting (CC) is a new method for approximating the p-th frequency moments of data streams. Our contributions include: 1) We prove that Renyi entropy is (much) better than Tsallis entropy for approximating Shannon entropy. 2) We propose the optimal quantile estimator for CC, which considerably improves the previous estimators. 3) Our experiments demonstrate that CC is indeed highly effective approximating the moments and entropies. We also demonstrate the crucial importance of utilizing the variance-bias trade-off.

Affiliated with

Also associated with

No associations

Rating

Estimating Entropy of Data Streams Using Compressed Counting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Estimating Entropy of Data Streams Using Compressed Counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating Entropy of Data Streams Using Compressed Counting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352860