Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges

Summary: SWTC introduces a sliding-window approach for approximate triangle counting in streaming graphs with duplicate edges. Fixed-length slicing delivers unbiased sampling and memory-bounded cardinality estimation, with theoretical guarantees and improved accuracy versus baselines under the same memory. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6081
Venue: SIGMOD
Year: 2021
Pagerank: 7.6321424e-05
Overall Rank: 3,063 | 78.70%
DOI: 10.1145/3448016.3452800

Incoming Non-self Citations Over Time

Authors

1. Xiangyang Gou
2. Lei Zou

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,657	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9720132e-05
7,576	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.7064285e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05
8,574	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	4.4930153e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
9,228	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3690661e-05
9,481	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3341665e-05
9,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1945683e-05
10,586	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.1945683e-05
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
589	Massive Graph Triangulation	2013	SIGMOD	0.00019576567
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
2,878	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9706235e-05
3,534	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	6.9997025e-05
4,879	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8575676e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,459	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1651553e-05
6,468	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.0526408e-05
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-05
10,586	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.1945683e-05
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1945683e-05
9,228	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3690661e-05
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
5,046	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7405307e-05
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
4,879	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8575676e-05