research-article

Declaring independence via the sketching of sketches

Authors:

Andrew McGregorAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 737 - 745

Published: 02 July 2019 Publication History

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]

N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie, Testing k-wise and almost k-wise independence., in STOC, 2007, pp. 496--505.

Digital Library

[2]

N. Alon, Y. Matias, and M. Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, 58 (1999), pp. 137--147.

Digital Library

[3]

R. Ananthakrishna, A. Das, J. Gehrke, F. Korn, S. Muthukrishnan, and D. Srivastava, Efficient approximation of correlated sums on data streams., IEEE Trans. Knowl. Data Eng., 15 (2003), pp. 569--572.

Digital Library

[4]

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, Models and issues in data stream systems, ACM Symposium on Principles of Database Systems, (2002), pp. 1--16.

Digital Library

[5]

Z. Bar-Yossef, R. Kumar, and D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, in ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 623--632.

Digital Library

[6]

T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White, Testing random variables for independence and identity., in FOCS, 2001, pp. 442--451.

Digital Library

[7]

L. Bhuvanagiri, S. Ganguly, D. Kesh, and C. Saha, Simpler algorithm for estimating frequency moments of data streams., in ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 708--713.

Digital Library

[8]

A. Chakrabarti, G. Cormode, and A. McGregor, A near-optimal algorithm for computing the entropy of a stream, in ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 328--335.

Digital Library

[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]

K. L. Chang and R. Kannan, The space complexity of pass-efficient algorithms for clustering., in ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1157--1166.

Digital Library

[11]

M. Charikar, C. Chekuri, T. Feder, and R. Motwani, Incremental clustering and dynamic information retrieval., SIAM J. Comput., 33 (2004), pp. 1417--1440.

Digital Library

[12]

M. Charikar, L. O'Callaghan, and R. Panigrahy, Better streaming algorithms for clustering problems., in ACM Symposium on Theory of Computing, 2003, pp. 30--39.

Digital Library

[13]

G. Cormode, M. Datar, P. Indyk, and S. Muthukrishnan, Comparing data streams using hamming norms (How to zero in)., IEEE Trans. Knowl. Data Eng., 15 (2003), pp. 529--540.

Digital Library

[14]

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava, Space- and time-efficient deterministic algorithms for biased quantiles over data streams., in ACM Symposium on Principles of Database Systems, 2006, pp. 263--272.

Digital Library

[15]

T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, 1991.

Digital Library

[16]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang, Graph distances in the streaming model: the value of space., in ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 745--754.

Digital Library

[17]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang, On graph problems in a semi-streaming model, Theoretical Computer Science, 348 (2005), pp. 207--216.

Digital Library

[18]

J. Gehrke, F. Korn, and D. Srivastava, On computing correlated aggregates over continual data streams., in SIGMOD Conference, 2001, pp. 13--24.

Digital Library

[19]

M. Greenwald and S. Khanna, Efficient online computation of quantile summaries., in ACM International Conference on Management of Data, 2001, pp. 58--66.

Digital Library

[20]

S. Guha, P. Indyk, and A. McGregor, Sketching information divergences, in Conference on Learning Theory, 2007, pp. 424--438.

Digital Library

[21]

S. Guha, N. Koudas, and K. Shim, Approximation and streaming algorithms for histogram construction problems, ACM Trans. Database Syst., 31 (2006), pp. 396--438.

Digital Library

[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.

Digital Library

[23]

S. Guha and A. McGregor, Space-efficient sampling, in AISTATS, 2007, pp. 169--176.

[24]

P. Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation., J. ACM, 53 (2006), pp. 307--323.

Digital Library

[25]

P. Indyk and D. P. Woodruff, Optimal approximations of the frequency moments of data streams., in ACM Symposium on Theory of Computing, 2005, pp. 202--208.

Digital Library

[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]

C. D. Manning and H. Schtze, Foundations of Statistical Natural Language Processing, MIT Press, 1999.

Digital Library

[28]

S. Muthukrishnan, Data streams: Algorithms and applications, Now Publishers, (2006).

Digital Library

[29]

D. P. Woodruff, Optimal space lower bounds for all frequency moments., in ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 167--175.

Digital Library

Cited By

Meister MSarlos TWoodruff DWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Tight dimensionality reduction for sketching low degree polynomial kernelsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455137(9475-9486)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455137
Kveton BMuthukrishnan SVu HXian YChampin PGandon FMédini LLalmas MIpeirotis P(2018)Finding Subcube Heavy Hitters in Analytics Data StreamsProceedings of the 2018 World Wide Web Conference10.1145/3178876.3186082(1705-1714)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3178876.3186082
Li YNguyen HWoodruff DChekuri C(2014)On sketching matrix norms and the top singular vectorProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634188(1562-1581)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634188
Show More Cited By

Index Terms

Declaring independence via the sketching of sketches

Recommendations

Architectural Drawing Using Pencil Sketches and AutoCAD
Sketching distributed sliding-window data streams

While traditional data management systems focus on evaluating single, ad hoc queries over static data sets in a centralized setting, several emerging applications require (possibly, continuous) answers to queries on dynamic data that is widely ...
Time-decaying sketches for sensor data aggregation
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

We present a new sketch for summarizing network data. The sketch has the following properties which make it useful in communication-efficient aggregation in distributed streaming scenarios, such as sensor networks: the sketch is duplicate-insensitive, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 02 July 2019

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meister MSarlos TWoodruff DWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Tight dimensionality reduction for sketching low degree polynomial kernelsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455137(9475-9486)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455137
Kveton BMuthukrishnan SVu HXian YChampin PGandon FMédini LLalmas MIpeirotis P(2018)Finding Subcube Heavy Hitters in Analytics Data StreamsProceedings of the 2018 World Wide Web Conference10.1145/3178876.3186082(1705-1714)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3178876.3186082
Li YNguyen HWoodruff DChekuri C(2014)On sketching matrix norms and the top singular vectorProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634188(1562-1581)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634188
Pagh R(2013)Compressed matrix multiplicationACM Transactions on Computation Theory10.1145/2493252.24932545:3(1-17)Online publication date: 22-Aug-2013
https://dl.acm.org/doi/10.1145/2493252.2493254
Batu TFortnow LRubinfeld RSmith WWhite P(2013)Testing Closeness of Discrete DistributionsJournal of the ACM10.1145/2432622.243262660:1(1-25)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1145/2432622.2432626
Pham NPagh RYang QAgarwal DPei J(2012)A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional dataProceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2339530.2339669(877-885)Online publication date: 12-Aug-2012
https://dl.acm.org/doi/10.1145/2339530.2339669
Pagh RGoldwasser S(2012)Compressed matrix multiplicationProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090271(442-451)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090271
Crouch MMcGregor A(2011)Periodicity and cyclic shifts via linear sketchesProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033267(158-170)Online publication date: 17-Aug-2011
https://dl.acm.org/doi/10.5555/2033252.2033267
Kane DNelson JPorat EWoodruff DFortnow LVadhan S(2011)Fast moment estimation in data streams in optimal spaceProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993735(745-754)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993735
Woodruff DFortnow LVadhan S(2011)Near-optimal private approximation protocols via a black box transformationProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993733(735-744)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993733
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents