Better Algorithms for Counting Triangles in Data Streams

Summary: Tightens space for 1+ε triangle-count approximation in streams: adjacency-list model achieves O~(ε^{-2} m / sqrt(T)) in one pass and O~(ε^{-2} m^{3/2} / T) in two passes; arbitrary-order achieves O~(ε^{-2} m / T) in two passes and O~(ε^{-2} m^{3/2} / T) in three passes (with degree oracle). Introduces an efficient wedge-sampling implementation via the first multi-sample l_p sampling algorithm with O(polylog n) update time, a broadly applicable primitive. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h55a8f990cad9d371
Venue: PODS
Year: 2016
Pagerank: 6.2182515e-05
Overall Rank: 5,232 | 64.83%
DOI: 10.1145/2902251.2902283

Incoming Non-self Citations Over Time

Authors

1. Andrew McGregor (University of Massachusetts Amherst)
2. Sofya Vorotnikova (University of Massachusetts Amherst)
3. Hoa T. Vu (University of Massachusetts Amherst)

BibTeX Citation

@inproceedings{mcgregor_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Better Algorithms for Counting Triangles in Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902283},
        doi = {10.1145/2902251.2902283},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {McGregor, Andrew and Vorotnikova, Sofya and Vu, Hoa T.},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
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
10,157	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	5.0706053e-05
11,829	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
462	Counting Triangles in Data Streams	2006	PODS	0.00017807125
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,603	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
2	4,575	On Sampling from Massive Graph Streams	2017	VLDB
3	11,829	Approximately Counting Subgraphs in Data Streams	2022	PODS
4	2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
5	6,385	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS
6	9,089	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
7	4,487	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
8	6,968	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
9	1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
10	462	Counting Triangles in Data Streams	2006	PODS