Counting and Sampling Triangles from a Graph Stream

Summary: Space-efficient streaming algorithm for counting and sampling triangles (and constant-sized cliques) in massive graphs, one-pass with low memory. Outperforms prior work in space and time, with a simple implementation and strong practical performance on large-scale data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10674
Venue: VLDB
Year: 2013
Pagerank: 0.00011907399
Overall Rank: 1,178 | 91.82%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,736	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.2521847e-05
4,453	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.7506837e-05
4,540	On Sampling from Massive Graph Streams	2017	VLDB	6.7090838e-05
4,930	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.5040855e-05
5,779	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	6.1549096e-05
6,236	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	6.0070757e-05
6,619	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.8801548e-05
7,042	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	5.7712457e-05
8,622	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.4598872e-05
8,846	Reservoir Sampling over Joins	2024	SIGMOD	5.4239669e-05
9,615	External Memory Stream Sampling	2015	PODS	5.3044777e-05
10,258	TIMEST: Temporal Information Motif Estimator Using Sampling Trees	2026	VLDB	5.1725247e-05
10,288	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	5.1725247e-05
10,495	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.1725247e-05
10,591	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.1725247e-05
10,594	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	5.1725247e-05
10,875	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	5.1725247e-05
11,323	Approximately Counting Subgraphs in Data Streams	2022	PODS	5.1725247e-05
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
454	Counting Triangles in Data Streams	2006	PODS	0.00018243292
1,339	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.0001120043

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	5.1725247e-05
9,241	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	5.3572577e-05
4,540	On Sampling from Massive Graph Streams	2017	VLDB	6.7090838e-05
8,622	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.4598872e-05
2,736	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.2521847e-05
6,236	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	6.0070757e-05
602	Massive Graph Triangulation	2013	SIGMOD	0.00015983188
4,453	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.7506837e-05
4,930	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.5040855e-05
454	Counting Triangles in Data Streams	2006	PODS	0.00018243292