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: 1677
Venue: PODS
Year: 2016
Pagerank: 6.3609746e-05
Overall Rank: 5,110 | 64.95%
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,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,967	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	5.1869874e-05
11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS	5.093636e-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
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
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

Semantically Similar Papers

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