Efficient Matrix Sketching over Distributed Data

Summary: Tight deterministic lower bound on communication for covariance sketches (||A^T A - B^T B||_2) in the s-server distributed model, proving a deterministic vs randomized gap. Randomized one-pass, low-space protocols bypass the bound to cut communication and improve distributed PCA. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdf5338e0ec42d19d
Venue: PODS
Year: 2017
Pagerank: 5.3148581e-05
Overall Rank: 8,459 | 43.30%
DOI: 10.1145/3034786.3056119

Incoming Non-self Citations Over Time

Authors

1. Zengfeng Huang (University of New South Wales)
2. Xuemin Lin (University of New South Wales)
3. Wenjie Zhang (University of New South Wales)
4. Ying Zhang (University of Technology Sydney)

BibTeX Citation

@inproceedings{huang_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Efficient Matrix Sketching over Distributed Data}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056119},
        doi = {10.1145/3034786.3056119},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Huang, Zengfeng and Lin, Xuemin and Zhang, Wenjie and Zhang, Ying},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,688	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
452	Mergeable Summaries	2012	PODS	0.00018032092
1,242	Communication Steps for Parallel Query Processing	2013	PODS	0.00011372366
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
6,082	Streaming Anomaly Detection Using Randomized Matrix Sketching	2016	VLDB	5.8754866e-05
6,136	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8578818e-05
6,855	Matrix Sketching Over Sliding Windows	2016	SIGMOD	5.6470368e-05
6,856	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6470368e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS
2	3,887	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD
3	5,505	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD
4	1,153	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS
5	2,720	Exploiting Matrix Dependency for Efficient Distributed Matrix Computation	2015	SIGMOD
6	5,929	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD
7	6,855	Matrix Sketching Over Sliding Windows	2016	SIGMOD
8	10,688	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD
9	8,732	sPCA: Scalable Principal Component Analysis for Big Data on Distributed Platforms	2015	SIGMOD
10	6,856	Continuous Matrix Approximation on Distributed Data	2014	VLDB