Approximately Counting Subgraphs in Data Streams

Summary: Reduction converting constant-round sublinear-time graph query algorithms into constant-pass sublinear-space streaming algorithms, relating query adaptivity to pass complexity. Yields a 3-pass turnstile (1±ε)-approx for #H in Õ(m^{ρ(H)}/(ε^2#H)) space (ρ(H)=fractional edge-cover) and a constant-pass K_r clique-counting algorithm in degeneracy λ, resolving the Bera–Seshadhri conjecture. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1871
Venue: PODS
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,520 | 20.97%
DOI: 10.1145/3517804.3524145

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Hendrik Fichtenberger (University of Vienna)
2. Pan Peng (University of Science and Technology Beijing)

BibTeX Citation

@inproceedings{fichtenberger_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Approximately Counting Subgraphs in Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524145},
        doi = {10.1145/3517804.3524145},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fichtenberger, Hendrik and Peng, Pan},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
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
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
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
2	4,613	On Sampling from Massive Graph Streams	2017	VLDB
3	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
4	458	Counting Triangles in Data Streams	2006	PODS
5	9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
6	2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
7	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
8	6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS
9	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
10	8,928	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS