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.00017799662
Overall Rank: 463 | 96.89%
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,042	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012331317
1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00011933948
1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011720594
1,415	Estimating PageRank on Graph Streams	2008	PODS	0.00010732327
2,102	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0433983e-05
2,168	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9292584e-05
2,421	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4859022e-05
2,626	Optimal Sampling from Sliding Windows	2009	PODS	8.205667e-05
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1492816e-05
3,381	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	7.3532839e-05
4,490	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.5755831e-05
4,577	On Sampling from Massive Graph Streams	2017	VLDB	6.5225284e-05
4,978	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.3283029e-05
5,237	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.2153078e-05
5,455	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1218783e-05
6,388	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.8024551e-05
6,969	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6289911e-05
8,652	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	5.2929907e-05
9,099	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.2258409e-05
9,234	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.2032182e-05
9,318	Revisiting Graph Analytics Benchmark	2025	SIGMOD	5.1944733e-05
11,261	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.9769913e-05
11,349	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB	4.9769913e-05
11,835	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9769913e-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.00026688651
193	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025647819
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,099	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
2	11,261	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB
3	4,577	On Sampling from Massive Graph Streams	2017	VLDB
4	8,652	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD
5	10,614	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
6	6,969	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,490	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
10	5,237	Better Algorithms for Counting Triangles in Data Streams	2016	PODS