A near-optimal algorithm for computing the entropy of a stream

ABSTRACT

We describe a simple algorithm for approximating the empirical entropy of a stream of m values in a single pass, using O(ε^-2 log(δ^-1) log m) words of space. Our algorithm is based upon a novel extension of a method introduced by Alon, Matias, and Szegedy [1]. We show a space lower bound of Ω(ε^-2 / log(ε^-1)), meaning that our algorithm is near-optimal in terms of its dependency on ε. This improves over previous work on this problem [8, 13, 17, 5]. We show that generalizing to kth order entropy requires close to linear space for all k ≥ 1, and give additive approximations using our algorithm. Lastly, we show how to compute a multiplicative approximation to the entropy of a random walk on an undirected graph.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: Brian Babcock , Mayur Datar , Rajeev Motwani, Sampling from a moving window over streaming data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.633-634, January 06-08, 2002, San Francisco, California
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 4: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 5: Lakshminath Bhuvanagiri , Sumit Ganguly, Estimating entropy over data streams, Proceedings of the 14th conference on Annual European Symposium, p.148-159, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_16]
• 6: Lakshminath Bhuvanagiri , Sumit Ganguly , Deepanjan Kesh , Chandan Saha, Simpler algorithm for estimating frequency moments of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.708-713, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109634]
• 7: P. Bose, E. Kranakis, P. Morin, and Y. Tang, Bounds for frequency estimation of packet streams, in SIROCCO, 2003.
• 8: A. Chakrabarti, K. Do Ba, and S. Muthukrishnan, Estimating entropy and entropy norm on data streams., in STACS, 2006, pp. 196--205.
• 9: A. Chakrabarti, S. Khot, and X. Sun, Near-optimal lower bounds on the multi-party communication complexity of set disjointness, in CCC, 2003, pp. 107--117.
• 10: Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065201]
• 11: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, On graph problems in a semi-streaming model, Theoretical Computer Science, v.348 n.2, p.207-216, 8 December 2005 [doi>10.1016/j.tcs.2005.09.013]
• 12: Y. Gu, A. McCallum, and D. Towsley, Detecting anomalies in network traffic using maximum entropy estimation., in Proc. Internet Measurement Conference, 2005.
• 13: Sudipto Guha , Andrew McGregor , Suresh Venkatasubramanian, Streaming and sublinear approximation of entropy and information distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.733-742, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109637]
• 14: Piotr Indyk, A small approximately min-wise independent family of hash functions, Journal of Algorithms, v.38 n.1, p.84-90, Jan. 2001 [doi>10.1006/jagm.2000.1131]
• 15: Piotr Indyk , David Woodruff, Tight Lower Bounds for the Distinct Elements Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.283, October 11-14, 2003
• 16: 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]
• 17: Ashwin Lall , Vyas Sekar , Mitsunori Ogihara , Jun Xu , Hui Zhang, Data streaming algorithms for estimating entropy of network traffic, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
• 18: J. Misra and D. Gries, Finding repeated elements, Science of Computer Programming, 2 (1982), pp. 143--152.
• 19: N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, 12 (1992), pp. 449--461.
• 20: Arno Wagner , Bernhard Plattner, Entropy Based Worm and Anomaly Detection in Fast IP Networks, Proceedings of the 14th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprise, p.172-177, June 13-15, 2005 [doi>10.1109/WETICE.2005.35]
• 21: 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
• 22: Kuai Xu , Zhi-Li Zhang , Supratik Bhattacharyya, Profiling internet backbone traffic: behavior models and applications, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA