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: h86b3d2dc41cba756
Venue: PODS
Year: 2006
Pagerank: 0.00017807125
Overall Rank: 462 | 96.90%
DOI: 10.1145/1142351.1142388

Incoming Non-self Citations Over Time

Authors

1. Luciana S. Buriol (Federal University of Santa Maria)
2. Gereon Frahling (University of Paderborn)
3. Stefano Leonardi (Sapienza University)
4. Alberto Marchetti-Spaccamela (Sapienza University)
5. Christian Sohler (University of Paderborn)

BibTeX Citation

@inproceedings{buriol_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Counting Triangles in Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142388},
        doi = {10.1145/1142351.1142388},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Buriol, Luciana S. and Frahling, Gereon and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Sohler, Christian},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000119396
1,169	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011726145
1,415	Estimating PageRank on Graph Streams	2008	PODS	0.00010737378
2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0476814e-05
2,166	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9334874e-05
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
2,624	Optimal Sampling from Sliding Windows	2009	PODS	8.2095532e-05
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1531412e-05
3,380	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	7.3567664e-05
4,487	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.5786974e-05
4,575	On Sampling from Massive Graph Streams	2017	VLDB	6.5256176e-05
4,976	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.3313001e-05
5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.2182515e-05
5,450	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1247776e-05
6,385	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.8052032e-05
6,968	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6316571e-05
8,645	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	5.2954976e-05
9,089	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.2283159e-05
9,224	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.2056825e-05
9,309	Revisiting Graph Analytics Benchmark	2025	SIGMOD	5.1969334e-05
11,253	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.9793485e-05
11,341	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB	4.9793485e-05
11,829	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9793485e-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.

Rank	Cited Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025659453
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,089	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
2	11,253	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB
3	4,575	On Sampling from Massive Graph Streams	2017	VLDB
4	8,645	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD
5	10,603	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
6	6,968	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
7	2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
8	1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
9	4,487	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
10	5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS