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: h5ee2ce40736a4b2d
Venue: SIGMOD
Year: 2016
Pagerank: 8.861907e-05
Overall Rank: 2,202 | 85.25%
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,996	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.8528809e-05
4,235	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.7032322e-05
4,485	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.5644966e-05
4,801	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.3940913e-05
5,102	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.2623372e-05
5,628	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0438005e-05
5,995	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.903845e-05
6,701	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.6877324e-05
6,838	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.6517516e-05
7,204	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5717429e-05
7,895	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.4152499e-05
8,840	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.2513168e-05
10,306	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	5.0294306e-05
11,578	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.9605343e-05
11,629	Poligras: Policy-based Graph Summarization	2024	VLDB	4.9605343e-05
12,202	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	4.9605343e-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.0012089097
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056028465
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
1,376	Query Preserving Graph Compression	2012	SIGMOD	0.00010857788
2,063	Space Efficient Mining of Multigraph Streams	2005	PODS	9.0815237e-05
2,430	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4651179e-05
3,549	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.1896874e-05
4,601	Event Pattern Matching over Graph Streams	2015	VLDB	6.4964963e-05
4,808	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.3914777e-05

Semantically Similar Papers

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