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,342 | An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication | 2025 | PODS | 4.1945683e-05 |
| 10,596 | Truss Decomposition in Hypergraphs | 2025 | VLDB | 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 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,094 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.00014129658 |
| 1,344 | Counting and Sampling Triangles from a Graph Stream | 2013 | VLDB | 0.00012473724 |
| 4,089 | On Dense Pattern Mining in Graph Streams [Extended Abstract] | 2010 | VLDB | 6.4587806e-05 |
| 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 |
Previous
Page 1 / 1
Next