Declaring independence via the sketching of sketches

ABSTRACT

We consider the problem of identifying correlations in data streams. Surprisingly, our work seems to be the first to consider this natural problem. In the centralized model, we consider a stream of pairs (i,j) ∈ [n]² whose frequencies define a joint distribution (X,Y). In the distributed model, each coordinate of the pair may appear separately in the stream. We present a range of algorithms for approximating to what extent X and Y are independent, i.e., how close the joint distribution is to the product of the marginals. We consider various measures of closeness including ℓ₁, ℓ₂, and the mutual information between X and Y. Our algorithms are based on "sketching sketches", i.e., composing small-space linear synopses of the distributions. Perhaps ironically, the biggest technical challenges that arise relate to ensuring that different components of our estimates are sufficiently independent.

REFERENCES

• 1: Noga Alon , Alexandr Andoni , Tali Kaufman , Kevin Matulef , Ronitt Rubinfeld , Ning Xie, Testing k-wise and almost k-wise independence, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250863]
• 2: 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]
• 3: Rohit Ananthakrishna , Abhinandan Das , Johannes Gehrke , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Efficient Approximation of Correlated Sums on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.569-572, March 2003 [doi>10.1109/TKDE.2003.1198391]
• 4: 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]
• 5: 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
• 6: T. Batu , L. Fortnow , E. Fischer , R. Kumar , R. Rubinfeld , P. White, Testing Random Variables for Independence and Identity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.442, October 14-17, 2001
• 7: 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]
• 8: Amit Chakrabarti , Graham Cormode , Andrew McGregor, A near-optimal algorithm for computing the entropy of a stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.328-335, January 07-09, 2007, New Orleans, Louisiana
• 9: A. Chakrabarti, S. Khot, and X. Sun, Near-optimal lower bounds on the multi-party communication complexity of set disjointness., in IEEE Conference on Computational Complexity, 2003, pp. 107--117.
• 10: Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1157-1166, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109685]
• 11: Moses Charikar , Chandra Chekuri , Tomas Feder , Rajeev Motwani, Incremental Clustering and Dynamic Information Retrieval, SIAM Journal on Computing, v.33 n.6, p.1417-1440, 2004 [doi>10.1137/S0097539702418498]
• 12: Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780548]
• 13: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March 2003 [doi>10.1109/TKDE.2003.1198388]
• 14: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Space- and time-efficient deterministic algorithms for biased quantiles over data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142389]
• 15: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 16: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 17: 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]
• 18: Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.13-24, May 21-24, 2001, Santa Barbara, California, United States
• 19: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 20: S. Guha, P. Indyk, and A. McGregor, Sketching information divergences, in Conference on Learning Theory, 2007, pp. 424--438.
• 21: Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006 [doi>10.1145/1132863.1132873]
• 22: S. Guha and A. McGregor, Lower bounds for quantile estimation in random-order and multipass streaming, in International Colloquium on Automata, Languages and Programming, 2007, pp. 704--715.
• 23: S. Guha and A. McGregor, Space-efficient sampling, in AISTATS, 2007, pp. 169--176.
• 24: 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]
• 25: 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]
• 26: T. S. Jayram, R. Kumar, and D. Sivakumar, Simple lower bound on one-way Gap-Hamming., in www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.
• 27: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 28: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 29: 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

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.2 Approximation

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Algorithms, Design, Theory