Compressed counting

ABSTRACT

We propose Compressed Counting (CC) for approximating the αth frequency moments (0 < α ≤ 2) of data streams under a relaxed strict-Turnstile model, using maximally-skewed stable random projections. Estimators based on the geometric mean and the harmonic mean are developed.

When α = 1, a simple counter suffices for counting the first moment (i.e., sum). The geometric mean estimator of CC has asymptotic variance α Δ = |α - 1|, capturing the intuition that the complexity should decrease as Δ = |α - 1| → 0. However, the previous classical algorithms based on symmetric stable random projections[12, 15] required O (1/ε²) space, in order to approximate the αth moments within a 1 + ε factor, for any 0 < α ≤ 2 including α = 1.

We show that using the geometric mean estimator, CC requires O [EQUATION] space, as Δ → 0. Therefore, in the neighborhood of α = 1, the complexity of CC is essentially O (1/ε) instead of O (1/ε²).

CC may be useful for estimating Shannon entropy, which can be approximated by certain functions of the αth moments with α → 1. [10, 9] suggested using α = 1 + Δ with (e.g.,) Δ < 0.0001 and ε < 10⁻⁷, to rigorously ensure reasonable approximations. Thus, unfortunately, CC is "theoretically impractical" for estimating Shannon entropy, despite its empirical success reported in [16].

REFERENCES

• 1: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An information statistics approach to data stream and communication complexity, Journal of Computer and System Sciences, v.68 n.4, p.702-732, June 2004 [doi>10.1016/j.jcss.2003.11.006]
• 5: J. M. Chambers, C. L. Mallows, and B. W. Stuck. A method for simulating stable random variables. JASA, 71(354):340--344, 1976.
• 6: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 7: Sumit Ganguly , Graham Cormode, On Estimating Frequency Moments of Data Streams, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_35]
• 8: I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Products. Academic Press, New York, 2000.
• 9: Nicholas J. A. Harvey , Jelani Nelson , Krzysztof Onak, Sketching and Streaming Entropy via Approximation Theory, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.489-498, October 25-28, 2008 [doi>10.1109/FOCS.2008.76]
• 10: N. J. A. Harvey, J. Nelson, and K. Onak. Streaming algorithms for estimating entropy. In ITW'08.
• 11: M. R. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on Data Streams. American Mathematical Society, 1999.
• 12: Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006 [doi>10.1145/1147954.1147955]
• 13: Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060621]
• 14: C. D. Hardin Jr. Skewed stable variables and processes. Technical Report 79, University of North Carolina, 1984.
• 15: Ping Li, Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 20-22, 2008, San Francisco, California
• 16: P. Li. A very efficient scheme for estimating entropy of data streams using compressed counting. arxiv.org/PS_cache/arxiv/pdf/0808/0808.1771v2.pdf, 2008.
• 17: P. Li, D. Paul, R. Narasimhan, and J. Cioffi. On the distribution of SINR for the MMSE MIMO receiver and performance analysis. IEEE Trans. Inform. Theory, 52(1):271--286, 2006.
• 18: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 19: A. Rényi. On measures of information and entropy. In The 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, 547--561, 1961.
• 20: Michael Saks , Xiaodong Sun, Space lower bounds for distance approximation in the data stream model, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509963]
• 21: C. Tsallis. Possible generalization of boltzmann-gibbs statistics. Journal of Statistical Physics, 52:479--487, 1988.
• 22: David Woodruff, Optimal space lower bounds for all frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 23: Haiquan (Chuck) Zhao , Ashwin Lall , Mitsunori Ogihara , Oliver Spatscheck , Jia Wang , Jun Xu, A data streaming algorithm for estimating entropies of od flows, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298345]
• 24: V. M. Zolotarev. One-dimensional Stable Distributions. American Mathematical Society, 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis