gSketch: On Query Estimation in Graph Streams

Summary: gSketch fuses traditional stream synopses with partitioned sketches to estimate queries on evolving graphs. It splits a global sketch into localized sketches to optimize accuracy under two scenarios: stream-only sampling, and joint stream+workload sampling, outperforming global baselines on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10629
Venue: VLDB
Year: 2012
Pagerank: 8.6710302e-05
Overall Rank: 2,377 | 83.70%
DOI: 10.14778/2078324.2078332

Incoming Non-self Citations Over Time

Authors

1. Peixiang Zhao (University of Illinois Urbana-Champaign)
2. Charu C. Aggarwal (IBM)
3. Min Wang (Hewlett Packard Enterprise)

BibTeX Citation

@article{zhao_vldb12,
        title = {{gSketch: On Query Estimation in Graph Streams}},
        author = {Zhao, Peixiang and Aggarwal, Charu C. and Wang, Min},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {3},
        pages = {193--204},
        doi = {10.14778/2078324.2078332},
        url = {https://doi.org/10.14778/2078324.2078332},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
594	Massive Graph Triangulation	2013	SIGMOD	0.00015979077
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-05
3,601	TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing	2019	VLDB	7.27018e-05
4,813	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.4974292e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-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
7,498	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.6031077e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,396	Estimating PageRank on Graph Streams	2008	PODS	0.00010921308
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05
4,236	On Dense Pattern Mining in Graph Streams	2010	VLDB	6.8164649e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD
2	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
3	2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD
4	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD
5	1,146	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS
6	7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB
7	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
9	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
10	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD