Back to papers
Counting Triangles in Data Streams
Summary: Two space-bounded random-sampling streaming algorithms for triangle counting: an order-agnostic method with space tied to triangles/(triples with ≥1 edge), and an incidence-stream method with space tied to triangles/length-2 paths and update time O(log|V|*(1+s|V|/|E|)). Scales with graph structure not |V|; implemented on graphs up to 1B edges and the incidence algorithm achieves ≲6% average error with s=10k.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1397
- Venue
- PODS
- Year
- 2006
- Pagerank
- 0.00024556183
- Overall Rank
- 392 | 97.28%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 24 of 24 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 595 |
Estimating PageRank on Graph Streams |
2008 |
PODS |
0.00019507721 |
| 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 |
| 1,500 |
Parallel Subgraph Listing in a Large-Scale Graph |
2014 |
SIGMOD |
0.00011674394 |
| 2,437 |
gSketch: On Query Estimation in Graph Streams |
2012 |
VLDB |
8.8231651e-05 |
| 2,789 |
Optimal Sampling from Sliding Windows |
2009 |
PODS |
8.1249652e-05 |
| 2,910 |
DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine |
2016 |
SIGMOD |
7.9266529e-05 |
| 2,997 |
Subgraph Matching: on Compression and Computation |
2018 |
VLDB |
7.7559339e-05 |
| 3,063 |
Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges |
2021 |
SIGMOD |
7.6321424e-05 |
| 3,220 |
Structural Trend Analysis for Online Social Networks |
2011 |
VLDB |
7.3531514e-05 |
| 3,534 |
OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs |
2014 |
SIGMOD |
6.9997025e-05 |
| 4,879 |
Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage |
2018 |
VLDB |
5.8575676e-05 |
| 4,898 |
On Sampling from Massive Graph Streams |
2017 |
VLDB |
5.8459467e-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 |
| 6,864 |
Triangle and Four Cycle Counting in the Data Stream Model |
2020 |
PODS |
4.9050236e-05 |
| 7,317 |
Accurate and Fast Approximate Graph Pattern Mining at Scale |
2025 |
VLDB |
4.7639399e-05 |
| 8,533 |
How the Degeneracy Helps for Triangle Counting in Graph Streams |
2020 |
PODS |
4.4937074e-05 |
| 9,228 |
Efficiently Counting Triangles in Large Temporal Graphs |
2025 |
SIGMOD |
4.3690661e-05 |
| 9,477 |
Revisiting Graph Analytics Benchmark |
2025 |
SIGMOD |
4.3341665e-05 |
| 10,342 |
An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication |
2025 |
PODS |
4.1945683e-05 |
| 10,586 |
GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs |
2025 |
VLDB |
4.1945683e-05 |
| 10,710 |
Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach |
2025 |
VLDB |
4.1945683e-05 |
| 11,321 |
Approximately Counting Subgraphs in Data Streams |
2022 |
PODS |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 8,533 |
How the Degeneracy Helps for Triangle Counting in Graph Streams |
2020 |
PODS |
4.4937074e-05 |
| 10,586 |
GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs |
2025 |
VLDB |
4.1945683e-05 |
| 4,898 |
On Sampling from Massive Graph Streams |
2017 |
VLDB |
5.8459467e-05 |
| 9,228 |
Efficiently Counting Triangles in Large Temporal Graphs |
2025 |
SIGMOD |
4.3690661e-05 |
| 10,123 |
Triangle Counting in Hypergraph Streams: A Complete and Practical Approach |
2026 |
SIGMOD |
4.1945683e-05 |
| 6,864 |
Triangle and Four Cycle Counting in the Data Stream Model |
2020 |
PODS |
4.9050236e-05 |
| 3,063 |
Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges |
2021 |
SIGMOD |
7.6321424e-05 |
| 1,344 |
Counting and Sampling Triangles from a Graph Stream |
2013 |
VLDB |
0.00012473724 |
| 4,879 |
Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage |
2018 |
VLDB |
5.8575676e-05 |
| 5,046 |
Better Algorithms for Counting Triangles in Data Streams |
2016 |
PODS |
5.7405307e-05 |