How the Degeneracy Helps for Triangle Counting in Graph Streams

Summary: Constant-pass streaming algorithm for (1±ε)-triangle counting with space O(m·κ/T), leveraging graph degeneracy κ to significantly improve upon prior m^{3/2}/T and m/√T bounds for low-degeneracy families (e.g., planar, minor-closed, preferential-attachment). Proven nearly-matching lower bound Ω(m·κ/T). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1828
Venue: PODS
Year: 2020
Pagerank: 5.3483178e-05
Overall Rank: 8,928 | 38.75%
DOI: 10.1145/3375395.3387665

Incoming Non-self Citations Over Time

Authors

1. Suman K. Bera (University of California Santa Cruz)
2. C. Seshadhri (University of California Santa Cruz)

BibTeX Citation

@inproceedings{bera_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{How the Degeneracy Helps for Triangle Counting in Graph Streams}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387665},
        doi = {10.1145/3375395.3387665},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bera, Suman K. and Seshadhri, C.},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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	9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS
2	2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS
3	6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
4	2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
5	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
6	6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS
7	458	Counting Triangles in Data Streams	2006	PODS
8	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
9	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
10	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS