Triangle and Four Cycle Counting in the Data Stream Model
Summary: Improved algorithms and matching lower bounds for triangle and 4‑cycle counting across arbitrary-, random-, and adjacency-list-order streams, yielding strictly better space/pass trade-offs. Highlights: single-pass (1+ε) triangles in random-order (optimal), adjacency-list single-pass/density 4‑cycle guarantees, and multi-/one-pass improvements and lower bounds for 4‑cycles in arbitrary order. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,354 | An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication | 2025 | PODS | 4.1905499e-05 |
| 10,604 | Truss Decomposition in Hypergraphs | 2025 | VLDB | 4.1905499e-05 |
| 11,323 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1905499e-05 |
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 |
|---|---|---|---|---|
| 389 | Counting Triangles in Data Streams | 2006 | PODS | 0.00024649634 |
| 922 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS | 0.00015254436 |
| 1,117 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.0001386123 |
| 1,348 | Counting and Sampling Triangles from a Graph Stream | 2013 | VLDB | 0.00012461666 |
| 4,092 | On Dense Pattern Mining in Graph Streams [Extended Abstract] | 2010 | VLDB | 6.4525563e-05 |
| 5,043 | Better Algorithms for Counting Triangles in Data Streams | 2016 | PODS | 5.7350154e-05 |
| 6,463 | The Complexity of Counting Cycles in the Adjacency List Streaming Model | 2019 | PODS | 5.0477915e-05 |
Previous
Page 1 / 1
Next