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.00011726145
Overall Rank: 1,169 | 92.15%
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 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000119396
4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6265793e-05
4,788	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.4141952e-05
4,846	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	6.3824495e-05
5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.2182515e-05
5,660	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0478621e-05
6,968	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6316571e-05
7,799	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	5.4510258e-05
7,849	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	5.4410785e-05
7,957	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.4183555e-05
8,211	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.3772821e-05
9,236	DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay	2024	SIGMOD	5.2056825e-05
10,369	Deterministic Lower Bounds for k-Edge Connectivity in the Distributed Sketching Model	2026	PODS	4.9793485e-05
11,094	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.9793485e-05
11,473	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut	2024	PODS	4.9793485e-05
11,829	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9793485e-05
12,197	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9793485e-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
462	Counting Triangles in Data Streams	2006	PODS	0.00017807125
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017387321
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
2,171	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9239861e-05
2,219	Optimal Sampling From Distributed Streams	2010	PODS	8.8156731e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,501	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
2	2,054	Space Efficient Mining of Multigraph Streams	2005	PODS
3	8,835	Efficient framework for operating on data sketches	2023	VLDB
4	561	Densest Subgraph in Streaming and MapReduce	2012	VLDB
5	8,477	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD
6	8,836	On the algebra of data sketches	2021	VLDB
7	1,187	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
8	2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB
9	4,788	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB
10	4,846	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS