{'fraction_non_alphanumeric': 0.05124863145821386, 'fraction_numerical': 0.019289922318961473, 'mean_word_length': 4.223856209150327, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving Compressed Counting

Compressed Counting (CC) [22] was recently proposed for estimating the ath frequency moments of data streams, where 0<a<= 2. CC can be used for estimating Shannon entropy, which can be approximated by certain functions of the ath frequency moments as a ->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.


Introduction
Real-world data are often dynamic and can be modeled as data streams [2,13,29]. For example, reported in Information Week (Jan 9, 2006), Wal-Mart refreshes sales data hourly, adding a billion records of data daily. Ming data streams in (e.g.,) 100 TB scale databases has become an important area of research, e.g., [1,6], as network data can easily reach that scale [37]. Search engines are a typical source of data streams [2].

Data Stream Models
The Turnstile model [29] is popular for data streams. The input stream a t = (i t , I t ), i t ∈ [1, D] arriving sequentially describes the underlying signal A, where the increment I t can be either positive (insertion) or negative (deletion). This model is particularly useful for describing the empirical distribution because A t could be viewed as dynamic histograms. In Web and network applications, D = 2 64 may be possible.
In many applications, the strict-Turnstile model suffices, which restricts that A t [i] ≥ 0 at all times. For example, in an online store, a user normally can not cancel an order unless she/he did place the order.
Compressed Counting (CC) assumes a relaxed strict-Turnstile model by enforcing A t [i] ≥ 0 only at a particular time t. For s = t, A s [i] can be arbitrary.

Frequency Moments of Data Streams
This study is mainly concerned with computing (approximating, estimating) the αth frequency moment where we drop the subscript t in the notation F t, (α) .
Clearly, F (α) can be obtained by using a (very long) vector of length D (e.g., D = 2 64 ). Because entries of A t [i] are frequently updated at high rate, computing F (α) using a small storage space and in one pass of the data is crucial. It is often the case that streaming data are not stored, even on disks [2]. The problem of approximating F (α) has been very heavily studied, e.g., [3,5,7,9,15,16,20,21,26,32,35].
Interestingly, the sum (e.g., α = 1) can be computed trivially using a simple counter, assuming the relaxed strict-Turnstile model, because Is. Thus, the problem of approximating F (α) around α = 1 becomes very interesting from a theoretical point of view. The problem of estimating F (α) around α = 1 is also practically important. For example, it is known that Shannon entropy can be estimated from certain functions of F (α) by letting α → 1.

Entropies of Data Streams
Shannon entropy is widely used for characterizing the distribution of data streams, especially in Web and networks [8,18,28,38]. The empirical Shannon entropy is defined as It is known that Shannon entropy may be approximated by Rényi entropy [30] or Tsallis entropy [34]. Rényi entropy [30], denoted by H α , is defined as Tsallis entropy [34], denoted by T α , is defined as, .
Thus, while we focuse on improving estimates of F (α) as α → 1, it is practically useful if our algorithm could also exhibit improvements for α away from 1.

Application: Anomaly Detection in Large-Scale Networks
Measuring entropies of network traffic data has become an important task for detecting anomalies, which include network failures and distributed denial of service (DDoS) attacks [4,8,17,18,36,38].
Anomaly events often change the distribution of network traffic. Therefore, the Turnstile model, which may be viewed as histograms, becomes useful in realtime network measurements/monitoring.
A recent study [38] applied symmetric stable random projections [15,21] to estimate the αth frequency moments F (α) and the Shannon entropy. One major problem they reported is that, to ensure a sufficient accuracy, the required sample size tend to be prohibitive, for example in the order of O(10 4 ).

Our Contributions
We provide a high-level description of the algorithm, based on maximally-skewed stable random projections [22], also called Compressed Counting (CC).
Conceptually, we can view the data stream A t as a vector ∈ R D and multiple it by a matrix R ∈ R D×k . The resultant projected vector has k "samples" and should be much easier to store if k is small (e.g., k = 100), compared to (e.g.,) D = 2 64 .
Of course, the matrix-vector multiplication X = R T A t is conducted incrementally. Recall the Turnstile model (1) adopts a linear updating rule and the matrix-vector multiplication is also linear. The matrix R should not be fully materialized. We only need to re-generate entries of R on the fly and update the corresponding elements in the stored vector X = (x 1 , x 2 , ..., x k ). This is the standard technique in data streams [15].
The entries of R are sampled i.i.d. from a maximally skewed stable distribution, i.e., r ij ∼ S(α, β, 1), which has three parameters: α specifies which F (α) we want to compute, β is the skewness parameter and is set to be β = 1, and the scale parameter is 1.
The next task is to estimate F (α) from X = (x 1 , x 2 , ..., x k ). We will review that, after projec- In other words, the scale parameter is the F (α) we are after.
The proposed algorithm (estimator) in this study is based on the optimal power of the samples, i.e., where λ * is carefully pre-chosen and fixed as a constant for each α. It is called the optimal power estimator because λ * = λ * (α) is chosen to minimize its asymptotic (as k → ∞) variance at each α.
In [22], two estimators were provided, based on the geometric meanF (α),gm ∝ k j=1 |x j | 1/k and the harmonic mean that, CC dramatically improves symmetric stable random projections as α → 1, and the optimal power estimator improves both the geometric mean and harmonic mean estimators of CC.
The left panel plots the V values for the geometric mean estimator, the harmonic mean estimator (for α < 1), and the optimal power estimator, along with the V values for the geometric mean estimator for symmetric stable random projections in [21] ("symmetric GM"). The right panel plots the ratios of the variances to better illustrate the significant improvement of the optimal power estimator, near α = 1 (and α < 1).
The improvement of the new estimatorF (α),op is highly significant when α → 1−. To better illustrate this result, the right panel of Figure 1 plots the ratios of the variances for directly comparing the geometric mean and harmonic mean estimators with the optimal power estimator. For example, when ∆ = 1 − α ≈ 0.01 (or 0.0001), the variance ratios are about 100 (or 10000). In other words, when α ≈ 0.99 (or 0.9999), the variance of the optimal power estimator is only about 1% (or 0.01%) of the variance of the geometric mean (or harmonic mean) estimator. This is a remarkable improvement and will be practically highly useful.

The Significance of the Improvement
We would like to introduce the theoretical results [11,12], which proposed the rigorous criterion on how to choose α so that the Tsallis entropy or Rényi entropy is close enough to Shannon entropy. Their results are based on the worst-case bias. In general, [11,12] proposed using α extremely close to 1, e.g., ∆ = |1 − α| < 0.0001 or even smaller.
Therefore, according to the criteria in [11,12], our proposed estimator would be very useful; whereas the previous estimators in [22] are not yet practical.
The rest of the paper is organized as follows. The methodologies of CC and two estimators are reviewed in Section 2. The new estimator based on the optimal power is presented in Section 3. We show in Section 4 that the optimal power estimator is statistically optimal when α = 0.5. Some experiments are provided in Section 5 to help demonstrate the remarkable improvements of the new algorithm for CC.

Review of Compressed Counting
Compressed Counting (CC) is based on maximallyskewed stable random projections.
Consider independent variables, Z 1 , Z 2 ∼ S(α, β = 1, 1). For any constants C 1 , C 2 ≥ 0, the "α-stability" follows from properties of Fourier transforms: When β = 0, the above stability holds even if C 1 and C 2 are negative. This is why symmetric stable random projections [15,21] can be applied to general data but CC is restricted to the relaxed strict-Turnstile model.

Random Projections
Conceptually, one can generate a matrix R ∈ R D×k and multiply it with the data stream A t , i.e., X = By property of Fourier transforms, the entries of X, whose scale parameter is exactly F (α) . Thus, CC boils down to a statistical estimation problem.
For real implementation, one should conduct R T A t incrementally. This is possible because the Turnstile model (1) is linear. For every incoming a t = (i t , I t ), we update x j ← x j + r i t j I t for j = 1 to k. Entries of R are generated on-demand as necessary.

The Efficiency in Processing Time
Prior to CC, the method of symmetric stable random projections was the standard algorithm in data stream computations. However, [9] commented that, when k is large, generating entries of R on-demand and multiplications r itj × I t , j = 1 to k, can be too prohibitive. An easy "fix" is to use k as small as possible, which is possible with CC when α ≈ 1.
At the same sample size k, all procedures of CC and symmetric stable random projections are the same except that the entries in R follow different distributions. Since CC is much more accurate especially when α ≈ 1, it requires a much smaller sample size k.

The Geometric Mean Estimator
which is unbiased and has asymptotic (i.e., as k → ∞) variance As α → 1, the asymptotic variance approaches zero.

The Harmonic Mean Estimator
which is asymptotically unbiased and has variance

Previous Estimators Are Inadequate
While the above two estimators are nice results, they are not adequate for estimating Shannon entropy H. From the definitions of Rényi entropy H α (3) and Tsallis entropy T α (4), we can see immediately that using the estimated H α and T α to approximate H, the estimation variances would be proportional to 1 (α−1) 2 , which blows up very quickly as α → 1. However, the estimation variance of the geometric mean estimator F (α),gm decreases to zero at the rate of O(|α − 1|), which is too slow to cancel According [11,12], if a high accuracy is required, we have to use α close 1, because the only way to reduce the "intrinsic bias," |H α −H| or |T α −H|, is to let α be close to 1 as possible. Therefore, we need better algorithms (estimators); and the optimal power estimator provides such an algorithm.

The Optimal Power Estimator
Recall the task is to estimate the scale parameter F (α) from k i.i.d. samples x j ∼ S α, β = 1, F (α) . The optimal power estimator is based on the fundamental results on the moments of stable distributions.
If Z ∼ S(α, β = 1, F (α) ), then for any −1 < λ < α, where In particular, if α < 1, then, for any −∞ < λ < α, The idea of the optimal power estimator is to first find an unbiased estimator of F λ (α) , which will be in the form of 1 k k i=1 |x j | λ * α , using the moment formulas in Lemma 1. Next, we apply () 1/λ operation to the estimator of F λ (α) to obtain a (biased) estimator of F (α) . The O 1 k bias can be removed by standard Taylor expansion method (the "Delta" method in statistics). Lemma 2 presents the optimal power estimator, taking into account of bias-correction.

Lemma 2
The optimal power estimator iŝ where the function G(λ) is defined in (5).
With bias-correction, the estimator becomeŝ whose bias and variance are The parameter λ * = λ * (α) is determined by solving an optimization problem: Although the expressions appear very sophisticated, the real computations only involve because all other terms are functions of λ * and α and can be pre-computed. This type of estimator was also proposed in [25], for symmetric stable random projections, which improved the estimators in [21] by merely 0 ∼ 30% (depending on α). The optimal power estimator in [25] had only finite moments to a rather limited order (which seriously affects statistical properties). In comparison, the improvements of the new optimal power estimator for CC would be, for example, 100-fold or more at α ≈ 1.
The theoretical analysis of this optimal power estimator is far more sophisticated, compared to [25]. When α > 1, we can see from Figure 1 that the improvement is not very significant (unless α is close to 2). Thus, our theoretical analysis of the optimal power estimator mainly focuses on α < 1.
For α < 1, Lemma 3 proves that the optimal power λ * < 0, implying that all moments exist, according to results in Lemma 1. Lemma 3 also proves that g (λ; α) is a convex function of λ for every α if α < 1.

Proof:
See Appendix B.
Therefore, if α < 1, the optimal power estimator has all the moments, suggesting that this estimator may have good statistical properties. Figure 1 (right panel) shows that as α → 1−, the improvements of the optimal power over previous estimators in [22] are substantial and will be practically highly useful.
When α = 0.5 and β = 1, the stable distribution is known as the Lévy distribution, whose the density function can be expressed in a closed-form: Lemma 4 derives the MLE and the moments. The proof (which is omitted) involves tedious algebraic work by applying general results in [33].

LI UAI 2009
The bias-corrected version iŝ The first four moments ofF (0.5),mle,c are

An Empirical Study
We used the Web crawl data from a chunk of D = 2 16 pages. That is, the data vector (of length D) represents the numbers of occurrences of a word in D = 2 16 documents. Here, we only use static data instead of real data streams. This is a valid experiment because we just need to compare the estimation accuracy.
We report the experiments for ∆ = 1 − α from 0.1 to 10 −5 , and k = 5, 10, 100, 1000, 4000. Our experiments show that even with small k, the optimal power estimator achieved good accuracies, in terms of the normalized mean square errors ( √ MSE, divided by the true value). We notice that the normalized MSEs are quite similar across different words. Thus, we only present the results for one word vector, for the word "RICE." Figure 3 presents the results on estimating frequency moments using both CC and symmetric stable random projections. As expected, CC considerably improves symmetric stable random projections and the optimal power estimator of CC considerably improves the geometric mean and harmonic mean estimators of CC. Also, the empirical MSEs matched the theoretical asymptotic variances well. Figure 4 presents the results on estimating Shannon entropy using the estimated Tsallis entropy. Again, we can see the huge improvements of CC over symmetric stable random projections and the improvements of optimal power estimator over the other two estimators of CC. When α is too close 1, the geometric mean and harmonic mean estimators exhibit very large errors because the variances grow up quickly as α → 1.
For example, suppose the required accuracy is normalized MSE< 10%. Using the optimal power estimator, it suffices to use only k = 10 samples, for this data  vector. However, using the geometric mean or the harmonic mean estimator, we should choose k = 1000 and a carefully chosen α because if α is too close to 1, the errors become very large (the bias-variance trade-off).
Suppose we instead use symmetric stable random pro-jections. We need to use a much larger k and very carefully select the α. If α = 0.99, even with k = 1000, the normalized MSE is 1.0, a very large error. Because the α which attains the smallest MSE is data-dependent, this optimal α is generally unknown and hence one may have to use very large k to ensure the accuracy.
Therefore, using CC with the optimal power estimator becomes particularly appealing, because one does not have to worry much about choosing the "best" α.
In this example, 0.99 ≤ α < 1 produced very stable estimates of the Shannon entropy.
There is still room for further substantial improvement. Figure 4 shows that, if a high accuracy is desired (e.g., normalized MSE < 1%), then a large k has to be used (e.g., k = 1000) even with the optimal power estimator. Figure 4 demonstrates that as ∆ becomes very small (e.g., ∆ < 10 −3 at k = 1000), the errors of the optimal power estimator decrease very slowly.

Conclusions
Data streams are common in real-world. Estimating frequency moments and entropies of data streams is an active area of research. Shannon entropy is important in many applications, for example, real-time mining/monitoring anomaly events (such as DDoS attacks) in large-scale networks. The performance of recent algorithms for estimating Shannon entropy is critically contingent on the quality of the estimated αth frequency moments near α = 1.
The main contribution is a new algorithm for improving Compressed Counting (CC), which was recently developed for approximating the αth frequency moments. Based on the optimal power of the samples maintained by CC, our algorithm is as simple as the previous algorithms in [22]. The improvements of the new algorithm is remarkable when α → 1−. For example, in terms of the variances, the improvement would be roughly 100-fold, when α = 0.99; and even larger improvements as α is more close to 1−.
While the theoretical analysis of the optimal power estimator is interesting, this new algorithm will have a practical impact in estimating entropy of data streams.
There are open problems. For example, what is the true sample complexity bound of CC? Also, our experiments demonstrate that if a high accuracy is desired, then we still need a large sample size k. Therefore, there is much need for future research.
Finally, as a reviewer pointed out, methods based on stable random projections have a limitation. If we need to compute the αth moments for 10 different α values, we have to conduct 10 different random projections and store 10 sets of samples. This is the price to pay in order to have algorithms with guaranteed accuracy regardless of the data distribution. In real applications, we sometimes have prior information about the data distribution. For example, large-scale data are often highly sparse. A line of algorithms named Conditional Random Sampling (CRS) [23,24] can be effective in processing sparse data.
A biased estimator of F (α) would be R (α),λ 1/λ , which has O 1 k bias. This bias can be removed to an extent by Taylor expansions [19, Theorem 6.1.1]. We call this new estimator the "fractional power" estimator: where we plug in the estimated F λ (α) . The asymptotic variance, Var F (α),f p,c,λ , would be The optimal λ, denoted by λ * , is then We denote byF (α),op,c the optimal fractional power estimatorF (α),f p,c,λ * .