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: hdff2e05012d294f3
Venue: PODS
Year: 2012
Pagerank: 0.00011763855
Overall Rank: 1,153 | 92.28%
DOI: 10.1145/2213556.2213560

Incoming Non-self Citations Over Time

Authors

1. Kook Jin Ahn (University of Pennsylvania)
2. Sudipto Guha (University of Pennsylvania)
3. Andrew McGregor (University of Massachusetts Amherst)

BibTeX Citation

@inproceedings{ahn_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Graph Sketches: Sparsification, Spanners, and Subgraphs}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213560},
        doi = {10.1145/2213556.2213560},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,125	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00011894507
4,390	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6110397e-05
4,808	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.3914777e-05
4,869	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	6.3587064e-05
5,258	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.1947561e-05
5,628	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0438005e-05
6,991	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6103782e-05
7,819	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	5.4305999e-05
7,869	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	5.4206136e-05
7,978	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.3978826e-05
8,236	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.3569644e-05
9,269	DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay	2024	SIGMOD	5.1860131e-05
10,394	Effective Structurally Similar Community Search in Large Temporal Graphs	2027	SIGMOD	4.9605343e-05
10,447	Deterministic Lower Bounds for k-Edge Connectivity in the Distributed Sketching Model	2026	PODS	4.9605343e-05
11,164	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.9605343e-05
11,531	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut	2024	PODS	4.9605343e-05
11,879	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9605343e-05
12,246	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9605343e-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
465	Counting Triangles in Data Streams	2006	PODS	0.00017754185
495	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017347522
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013752994
2,184	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.8972748e-05
2,230	Optimal Sampling From Distributed Streams	2010	PODS	8.7889857e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,459	Efficient Matrix Sketching over Distributed Data	2017	PODS
2	2,063	Space Efficient Mining of Multigraph Streams	2005	PODS
3	8,862	Efficient framework for operating on data sketches	2023	VLDB
4	560	Densest Subgraph in Streaming and MapReduce	2012	VLDB
5	8,499	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD
6	8,863	On the algebra of data sketches	2021	VLDB
7	1,179	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
8	2,430	gSketch: On Query Estimation in Graph Streams	2012	VLDB
9	4,808	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB
10	4,869	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS