en
0.25
0.5
0.75
1.25
1.5
1.75
2
A New Algorithm for Compressed Counting with Applications in Shannon Entropy Estimation in Dynamic Data
Published on Aug 02, 20113555 Views
In this paper, we propose a new accurate algorithm for Compressed Counting, whose sample complexity is only O (1/v2) for v-additive Shannon entropy estimation. The constant factor for this bound is
Related categories
Chapter list
A New Algorithm for Compressed Counting00:00
Problem Statement00:00
Data Streams and the Turnstile Model00:49
A Cartoon Illustration of the Turnstile Data Stream Model02:52
Network Traffic, Data Streams, and Anomaly Detections03:55
Entropy and DDoS Attack04:44
IP source address packet entropy (time) history05:34
Outline of Our Approach06:23
Compressed Counting (CC)07:51
Why Linear Stable Random Projection Works?10:59
Previous Algorithms for Compressed Counting (CC)12:58
Comparison With Symmetric Stable Random Projections13:34
An Empirical Study - 115:15
An Empirical Study - 216:31
Entropy Estimation Using Symmetric Stable Projections16:58
Entropy Estimation Using CC with Geometric Mean Estimator17:59
Entropy Estimation Using CC with the New Estimator18:26
Shannon Entropy Estimation Results for All Vectors - 119:06
Shannon Entropy Estimation Results for All Vectors - 219:24
Shannon Entropy Estimation Results for All Vectors - 319:27
Shannon Entropy Estimation Results for All Vectors - 419:28
How to Choose Δ = 1 − α and Sample Size k?19:29
Statistical Optimality of the New Estimator of CC - 121:49
Statistical Optimality of the New Estimator of CC - 222:15