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: 1396
Venue: PODS
Year: 2006
Pagerank: 0.0001810876
Overall Rank: 458 | 96.86%
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,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012499878
1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000121583
1,146	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011984702
1,396	Estimating PageRank on Graph Streams	2008	PODS	0.00010921308
2,119	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.141144e-05
2,187	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9966682e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.3200595e-05
3,393	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	7.45141e-05
4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.6603827e-05
4,613	On Sampling from Massive Graph Streams	2017	VLDB	6.6071509e-05
4,855	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.4766126e-05
5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.3609746e-05
5,506	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1925892e-05
6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.9000002e-05
6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.7495468e-05
8,928	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.3483178e-05
9,048	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.3251649e-05
9,375	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	5.2755515e-05
9,622	Revisiting Graph Analytics Benchmark	2025	SIGMOD	5.2434488e-05
10,847	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	5.093636e-05
10,954	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB	5.093636e-05
11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS	5.093636e-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
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,928	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
2	10,847	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB
3	4,613	On Sampling from Massive Graph Streams	2017	VLDB
4	9,375	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD
5	10,411	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
6	6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
7	2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
8	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
9	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
10	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS