Triangle and Four Cycle Counting in the Data Stream Model

Summary: Improved algorithms and matching lower bounds for triangle and 4‑cycle counting across arbitrary-, random-, and adjacency-list-order streams, yielding strictly better space/pass trade-offs. Highlights: single-pass (1+ε) triangles in random-order (optimal), adjacency-list single-pass/density 4‑cycle guarantees, and multi-/one-pass improvements and lower bounds for 4‑cycles in arbitrary order. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1815
Venue: PODS
Year: 2020
Pagerank: 5.7495468e-05
Overall Rank: 6,873 | 52.85%
DOI: 10.1145/3375395.3387652

Incoming Non-self Citations Over Time

Authors

1. Andrew McGregor (University of Massachusetts Amherst)
2. Sofya Vorotnikova (Dartmouth College)

BibTeX Citation

@inproceedings{mcgregor_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{Triangle and Four Cycle Counting in the Data Stream Model}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387652},
        doi = {10.1145/3375395.3387652},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {McGregor, Andrew and Vorotnikova, Sofya},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,048	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.3251649e-05
10,857	Truss Decomposition in Hypergraphs	2025	VLDB	5.093636e-05
11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
4,236	On Dense Pattern Mining in Graph Streams	2010	VLDB	6.8164649e-05
5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.3609746e-05
6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.9000002e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
2	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
3	9,048	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS
4	8,928	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
5	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
6	8,744	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS
7	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
8	458	Counting Triangles in Data Streams	2006	PODS
9	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
10	6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS