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: 6082
Venue: SIGMOD
Year: 2021
Pagerank: 7.6247945e-05
Overall Rank: 3,067 | 78.69%
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,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
7,581	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.701915e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05
8,571	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	4.4887087e-05
8,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
9,231	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3648789e-05
9,483	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3300131e-05
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1905499e-05
10,594	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.1905499e-05
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	4.1905499e-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
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
588	Massive Graph Triangulation	2013	SIGMOD	0.00019588834
1,348	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012461666
1,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
2,068	Optimal Sampling From Distributed Streams	2010	PODS	9.638573e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
2,881	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9671512e-05
3,537	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	6.9929946e-05
4,883	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8519327e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,460	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1592411e-05
6,463	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.0477915e-05
11,323	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1905499e-05
10,594	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.1905499e-05
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1905499e-05
9,231	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3648789e-05
1,348	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012461666
5,043	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7350154e-05
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
4,883	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8519327e-05