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.8916948e-05
Overall Rank: 2,186 | 85.31%
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,980	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.8788724e-05
4,237	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.7107028e-05
4,587	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.5161686e-05
4,779	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.4163774e-05
5,075	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.2860889e-05
5,660	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0478621e-05
5,984	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.926237e-05
6,687	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.7079296e-05
6,816	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.6731874e-05
7,180	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5928753e-05
7,873	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.4357887e-05
8,813	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.2711766e-05
10,273	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	5.0485061e-05
11,523	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.9793485e-05
11,574	Poligras: Policy-based Graph Summarization	2024	VLDB	4.9793485e-05
12,153	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	4.9793485e-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.0012092602
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00055962491
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
2,054	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1135465e-05
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
3,540	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.2161972e-05
4,583	Event Pattern Matching over Graph Streams	2015	VLDB	6.5187824e-05
4,788	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.4141952e-05

Semantically Similar Papers

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