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: 1559
Venue: PODS
Year: 2012
Pagerank: 0.00011984702
Overall Rank: 1,146 | 92.14%
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,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000121583
4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.7786745e-05
4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.5587201e-05
4,739	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	6.5285049e-05
5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.3609746e-05
5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0994565e-05
6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.7495468e-05
7,647	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	5.5761394e-05
7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	5.5657914e-05
7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.5422948e-05
8,046	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.5007031e-05
9,056	DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay	2024	SIGMOD	5.3251649e-05
10,152	Deterministic Lower Bounds for k-Edge Connectivity in the Distributed Sketching Model	2026	PODS	5.093636e-05
10,651	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	5.093636e-05
11,125	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut	2024	PODS	5.093636e-05
11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS	5.093636e-05
11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	5.093636e-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
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
2	2,013	Space Efficient Mining of Multigraph Streams	2005	PODS
3	8,666	Efficient framework for operating on data sketches	2023	VLDB
4	564	Densest Subgraph in Streaming and MapReduce	2012	VLDB
5	8,310	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD
6	8,667	On the algebra of data sketches	2021	VLDB
7	1,163	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
8	2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB
9	4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB
10	4,739	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS