The Complexity of Counting Cycles in the Adjacency List Streaming Model

Summary: Characterizes sublinear-space complexity of cycle counting in the adjacency-list streaming model: provides a two-pass triangle estimator using Õ(m / T^{2/3}) space. Proves no sublinear multipass algorithms for l-cycles (l≥5); 4-cycles are intermediate—sublinear in multipass but impossible in single-pass. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1800
Venue: PODS
Year: 2019
Pagerank: 5.9000002e-05
Overall Rank: 6,363 | 56.35%
DOI: 10.1145/3294052.3319706

Incoming Non-self Citations Over Time

Authors

1. John Kallaugher (University of Texas)
2. Andrew McGregor (University of Massachusetts Amherst)
3. Eric Price (University of Texas)
4. Sofya Vorotnikova (University of Massachusetts Amherst)

BibTeX Citation

@inproceedings{kallaugher_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{The Complexity of Counting Cycles in the Adjacency List Streaming Model}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319706},
        doi = {10.1145/3294052.3319706},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kallaugher, John and McGregor, Andrew and Price, Eric and Vorotnikova, Sofya},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,506	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1925892e-05
6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.7495468e-05
9,048	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.3251649e-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
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000121583
5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.3609746e-05

Semantically Similar Papers

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