Graph Stream Summarization: From Big Bang to Big Crunch

Summary: TCM: graph stream summarization for directed/undirected graphs with sublinear space, linear construction, constant-time per-edge updates via joint node–edge summarization. A graphical sketch binds edge connections and cross-element node relations; enables diverse queries with error bounds and outperforms independent-element sketches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5312
Venue: SIGMOD
Year: 2016
Pagerank: 9.0825156e-05
Overall Rank: 2,148 | 85.27%
DOI: 10.1145/2882903.2915223

Incoming Non-self Citations Over Time

Authors

1. Nan Tang (Hamad Bin Khalifa University; Qatar Computing Research Institute)
2. Qing Chen (Hamad Bin Khalifa University; Qatar Computing Research Institute)
3. Prasenjit Mitra (Hamad Bin Khalifa University; Qatar Computing Research Institute)

BibTeX Citation

@inproceedings{tang_sigmod16,
        title = {{Graph Stream Summarization: From Big Bang to Big Crunch}},
        author = {Tang, Nan and Chen, Qing and Mitra, Prasenjit},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915223},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915223},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,898	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	7.0367583e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
4,722	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.5438628e-05
4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.4303691e-05
4,995	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.4089186e-05
5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0994565e-05
5,870	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	6.061038e-05
6,566	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.8381749e-05
6,685	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.8034001e-05
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
7,716	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.5605526e-05
8,647	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.3921304e-05
11,178	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	5.093636e-05
11,236	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	5.093636e-05
11,241	Poligras: Policy-based Graph Summarization	2024	VLDB	5.093636e-05
11,853	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	5.093636e-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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
1,336	Query Preserving Graph Compression	2012	SIGMOD	0.00011118804
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05
4,503	Event Pattern Matching over Graph Streams	2015	VLDB	6.6597953e-05
4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.5587201e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB
2	4,236	On Dense Pattern Mining in Graph Streams	2010	VLDB
3	4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD
4	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
5	486	Efficient Aggregation for Graph Summarization	2008	SIGMOD
6	6,266	Utility-Driven Graph Summarization	2019	VLDB
7	2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB
8	9,872	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB
9	5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB
10	2,013	Space Efficient Mining of Multigraph Streams	2005	PODS