Sketching Streams Through the Net: Distributed Approximate Query Tracking

Summary: Distributed tracking of complex aggregates over streams; space/time and network-efficient with provable error guarantees. Sketch-based, randomized summaries with local predictors enable low-overhead, accurate tracking for joins and wavelets—first distributed-streams approach. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hde7dd0983fc0697c
Venue: VLDB
Year: 2005
Pagerank: 0.00012187242
Overall Rank: 1,067 | 92.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Minos Garofalakis (Intel)

BibTeX Citation

@article{cormode_vldb05,
        title = {{Sketching Streams Through the Net: Distributed Approximate Query Tracking}},
        author = {Cormode, Graham and Garofalakis, Minos},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {13--24},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 36 of 36 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,470	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.00010555702
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9056116e-05
2,221	Optimal Sampling From Distributed Streams	2010	PODS	8.8114999e-05
2,360	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.5774153e-05
3,918	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9234041e-05
3,928	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9160175e-05
4,306	The Adversarial Robustness of Sampling	2020	PODS	6.6735594e-05
4,448	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5938243e-05
4,981	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3271e-05
5,006	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3159614e-05
5,120	Shape Sensitive Geometric Monitoring	2008	PODS	6.2639656e-05
5,197	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2316663e-05
5,379	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1540191e-05
6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.8769926e-05
6,838	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6657713e-05
7,017	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.6179674e-05
7,218	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.5810969e-05
7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5392867e-05
7,434	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5267207e-05
7,572	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.492682e-05
7,628	Distributed Online Tracking	2015	SIGMOD	5.4797177e-05
8,042	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.3999898e-05
8,430	Sampling Methods for Inner Product Sketching	2024	VLDB	5.3324907e-05
8,484	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.330748e-05
8,522	Optimistic Data Parallelism for FPGA-Accelerated Sketching	2023	VLDB	5.3225121e-05
8,676	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	5.2893101e-05
8,822	Bias-Aware Sketches	2017	VLDB	5.2692495e-05
8,851	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2634608e-05
9,047	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.2306775e-05
9,897	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.1125291e-05
9,900	Approximate Sketches	2024	SIGMOD	5.1110481e-05
10,518	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	4.9769913e-05
12,011	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9769913e-05
12,355	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	4.9769913e-05
12,905	GS-TMS: A Global Stream-based Threat Monitor System	2008	VLDB	4.9769913e-05
12,919	Public Health for the Internet (phi): Towards A New Grand Challenge for Information Management	2007	CIDR	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035962466
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023425462
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020510274
429	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018445263
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016288995
735	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014367765
743	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014309723
843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013534623
850	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013482116
1,434	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010663712
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4213787e-05
5,655	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0478521e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	565	Distributed Top-K Monitoring	2003	SIGMOD
2	14,156	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2006	VLDB
3	735	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
4	12,452	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB
5	7,875	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
7	7,434	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD
8	2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
9	12,355	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
10	7,921	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB