Approximately Counting Subgraphs in Data Streams
Summary: Reduction converting constant-round sublinear-time graph query algorithms into constant-pass sublinear-space streaming algorithms, relating query adaptivity to pass complexity. Yields a 3-pass turnstile (1±ε)-approx for #H in Õ(m^{ρ(H)}/(ε^2#H)) space (ρ(H)=fractional edge-cover) and a constant-pass K_r clique-counting algorithm in degeneracy λ, resolving the Bera–Seshadhri conjecture. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 392 | Counting Triangles in Data Streams | 2006 | PODS | 0.00024556183 |
| 1,040 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS | 0.00014488943 |
| 1,344 | Counting and Sampling Triangles from a Graph Stream | 2013 | VLDB | 0.00012473724 |
| 5,046 | Better Algorithms for Counting Triangles in Data Streams | 2016 | PODS | 5.7405307e-05 |
| 6,468 | The Complexity of Counting Cycles in the Adjacency List Streaming Model | 2019 | PODS | 5.0526408e-05 |
| 6,864 | Triangle and Four Cycle Counting in the Data Stream Model | 2020 | PODS | 4.9050236e-05 |
| 8,533 | How the Degeneracy Helps for Triangle Counting in Graph Streams | 2020 | PODS | 4.4937074e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,864 | Triangle and Four Cycle Counting in the Data Stream Model | 2020 | PODS | 4.9050236e-05 |
| 4,898 | On Sampling from Massive Graph Streams | 2017 | VLDB | 5.8459467e-05 |
| 1,344 | Counting and Sampling Triangles from a Graph Stream | 2013 | VLDB | 0.00012473724 |
| 392 | Counting Triangles in Data Streams | 2006 | PODS | 0.00024556183 |
| 8,905 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.427232e-05 |
| 3,063 | Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges | 2021 | SIGMOD | 7.6321424e-05 |
| 4,879 | Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage | 2018 | VLDB | 5.8575676e-05 |
| 6,468 | The Complexity of Counting Cycles in the Adjacency List Streaming Model | 2019 | PODS | 5.0526408e-05 |
| 5,046 | Better Algorithms for Counting Triangles in Data Streams | 2016 | PODS | 5.7405307e-05 |
| 8,533 | How the Degeneracy Helps for Triangle Counting in Graph Streams | 2020 | PODS | 4.4937074e-05 |