Graph Sketches: Sparsification, Spanners, and Subgraphs

Summary: Presents graph sketches via linear projections: Õ(n ε^{-2}) random linear measurements suffice to build (1+ε)-approximate cut sparsifiers and O(ε^{-2}) measurements give additive estimates of small induced subgraph counts. Introduces adaptive-sketch spanner constructions for distances and shows these non/adaptive sketches yield single-pass dynamic-stream and low-round distributed/MapReduce algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1560
Venue: PODS
Year: 2012
Pagerank: 0.00015254436
Overall Rank: 922 | 93.60%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,348	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012461666
4,399	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2134435e-05
4,906	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	5.8369374e-05
5,043	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7350154e-05
5,975	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2452824e-05
6,758	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9335749e-05
6,864	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	4.9003179e-05
7,033	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	4.8514885e-05
7,146	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8133378e-05
7,729	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	4.6614672e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05
8,903	DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay	2024	SIGMOD	4.4229886e-05
10,370	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1905499e-05
10,907	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut	2024	PODS	4.1905499e-05
11,323	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
449	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00022914472
1,117	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001386123
2,068	Optimal Sampling From Distributed Streams	2010	PODS	9.638573e-05
2,269	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1507118e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,952	Efficient Matrix Sketching over Distributed Data	2017	PODS	4.6089395e-05
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
8,445	Efficient framework for operating on data sketches	2023	VLDB	4.5042806e-05
645	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018727714
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.3997447e-05
8,446	On the algebra of data sketches	2021	VLDB	4.5042806e-05
773	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.00016788213
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
4,906	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	5.8369374e-05
7,033	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	4.8514885e-05