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: h77b5292fae500a7c
Venue: VLDB
Year: 2013
Pagerank: 0.00011933948
Overall Rank: 1,121 | 92.47%
DOI: 10.14778/2556549.2556571

Incoming Non-self Citations Over Time

Authors

1. A. Pavan (Iowa State University)
2. Kanat Tangwongsan (IBM)
3. Srikanta Tirthapura (Iowa State University)
4. Kun-Lung Wu (IBM)

BibTeX Citation

@article{pavan_vldb13,
        title = {{Counting and Sampling Triangles from a Graph Stream}},
        author = {Pavan, A. and Tangwongsan, Kanat and Tirthapura, Srikanta and Wu, Kun-Lung},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1870--1881},
        doi = {10.14778/2556549.2556571},
        url = {https://doi.org/10.14778/2556549.2556571},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1492816e-05
4,490	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.5755831e-05
4,577	On Sampling from Massive Graph Streams	2017	VLDB	6.5225284e-05
5,237	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.2153078e-05
5,455	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1218783e-05
5,984	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.9234316e-05
6,388	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.8024551e-05
6,969	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6289911e-05
7,471	Reservoir Sampling over Joins	2024	SIGMOD	5.5172544e-05
9,099	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS	5.2258409e-05
9,875	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.115241e-05
9,910	External Memory Stream Sampling	2015	PODS	5.1082848e-05
10,061	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.0851868e-05
10,420	An Efficient Streaming Algorithm for Approximating Graphlet Distributions	2026	SIGMOD	4.9769913e-05
10,738	TIMEST: Temporal Information Motif Estimator Using Sampling Trees	2026	VLDB	4.9769913e-05
10,803	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	4.9769913e-05
11,261	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.9769913e-05
11,452	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.9769913e-05
11,835	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.9769913e-05
12,065	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.9769913e-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
463	Counting Triangles in Data Streams	2006	PODS	0.00017799662
1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011720594

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,614	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
2	8,652	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD
3	4,577	On Sampling from Massive Graph Streams	2017	VLDB
4	9,099	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
5	2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD
6	6,388	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS
7	600	Massive Graph Triangulation	2013	SIGMOD
8	4,490	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
9	5,237	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
10	463	Counting Triangles in Data Streams	2006	PODS