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: 1678
Venue: PODS
Year: 2016
Pagerank: 5.7405307e-05
Overall Rank: 5,046 | 64.90%
DOI: 10.1145/2902251.2902283

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,468	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.0526408e-05
6,864	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	4.9050236e-05
8,533	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	4.4937074e-05
9,802	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	4.2807806e-05
10,342	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	4.1945683e-05
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-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
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1945683e-05
4,898	On Sampling from Massive Graph Streams	2017	VLDB	5.8459467e-05
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-05
3,063	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	7.6321424e-05
6,468	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.0526408e-05
8,533	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	4.4937074e-05
4,879	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8575676e-05
6,864	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	4.9050236e-05
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183