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: 1731
Venue: PODS
Year: 2017
Pagerank: 4.613363e-05
Overall Rank: 7,949 | 44.71%
DOI: 10.1145/3034786.3056119

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,138	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.1945683e-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
402	Mergeable Summaries	2012	PODS	0.00024196343
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
5,902	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2796864e-05
5,984	Streaming Anomaly Detection Using Randomized Matrix Sketching	2016	VLDB	5.244512e-05
6,602	Continuous Matrix Approximation on Distributed Data	2014	VLDB	4.9971153e-05
6,774	Matrix Sketching Over Sliding Windows	2016	SIGMOD	4.9299348e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,215	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	4.3716847e-05
3,808	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7455428e-05
6,191	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD	5.1642282e-05
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
2,848	Exploiting Matrix Dependency for Efficient Distributed Matrix Computation	2015	SIGMOD	8.0208832e-05
6,085	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	5.2195267e-05
6,774	Matrix Sketching Over Sliding Windows	2016	SIGMOD	4.9299348e-05
10,138	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.1945683e-05
8,300	sPCA: Scalable Principal Component Analysis for Big Data on Distributed Platforms	2015	SIGMOD	4.5435639e-05
6,602	Continuous Matrix Approximation on Distributed Data	2014	VLDB	4.9971153e-05