Database Paper Browser

Back to papers

Graph Sketches: Sparsification, Spanners, and Subgraphs

Summary: Presents graph sketches via linear projections: Õ(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.00014488943
Overall Rank
1,040 | 92.77%
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,344 Counting and Sampling Triangles from a Graph Stream 2013 VLDB 0.00012473724
4,403 A Framework for Adversarially Robust Streaming Algorithms 2020 PODS 6.2194225e-05
4,900 Graph Synopses, Sketches, and Streams: A Survey 2012 VLDB 5.8423536e-05
5,046 Better Algorithms for Counting Triangles in Data Streams 2016 PODS 5.7405307e-05
5,968 Summarizing Static and Dynamic Big Graphs 2017 VLDB 5.2503253e-05
6,755 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 4.9383139e-05
6,864 Triangle and Four Cycle Counting in the Data Stream Model 2020 PODS 4.9050236e-05
7,031 Vertex and Hyperedge Connectivity in Dynamic Graph Streams 2015 PODS 4.8561505e-05
7,145 Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model 2019 PODS 4.8179617e-05
7,769 GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams 2022 SIGMOD 4.6562896e-05
8,170 LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs 2024 VLDB 4.5697385e-05
8,902 DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay 2024 SIGMOD 4.427232e-05
10,358 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 4.1945683e-05
10,903 Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut 2024 PODS 4.1945683e-05
11,321 Approximately Counting Subgraphs in Data Streams 2022 PODS 4.1945683e-05
Previous Page 1 / 1 Next

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
383 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00024820873
392 Counting Triangles in Data Streams 2006 PODS 0.00024556183
1,094 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.00014129658
2,080 Optimal Sampling From Distributed Streams 2010 PODS 9.5899129e-05
2,282 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1073603e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,949 Efficient Matrix Sketching over Distributed Data 2017 PODS 4.613363e-05
1,472 Space Efficient Mining of Multigraph Streams 2005 PODS 0.00011828662
8,451 Efficient framework for operating on data sketches 2023 VLDB 4.5086031e-05
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
9,041 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 4.4039656e-05
8,452 On the algebra of data sketches 2021 VLDB 4.5086031e-05
777 Local Graph Sparsification for Scalable Clustering 2011 SIGMOD 0.0001679862
2,437 gSketch: On Query Estimation in Graph Streams 2012 VLDB 8.8231651e-05
4,900 Graph Synopses, Sketches, and Streams: A Survey 2012 VLDB 5.8423536e-05
7,031 Vertex and Hyperedge Connectivity in Dynamic Graph Streams 2015 PODS 4.8561505e-05