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.00012192801
Overall Rank: 1,066 | 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.00010560701
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9088372e-05
2,219	Optimal Sampling From Distributed Streams	2010	PODS	8.8156731e-05
2,359	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.5813849e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
3,927	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9192361e-05
4,305	The Adversarial Robustness of Sampling	2020	PODS	6.67672e-05
4,446	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5969248e-05
4,979	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3300966e-05
5,003	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3188773e-05
5,117	Shape Sensitive Geometric Monitoring	2008	PODS	6.2669323e-05
5,196	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2346177e-05
5,373	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1569337e-05
6,122	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.879545e-05
6,833	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6684547e-05
7,016	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.6206282e-05
7,216	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.5837401e-05
7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5418075e-05
7,431	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5293382e-05
7,566	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.4952834e-05
7,622	Distributed Online Tracking	2015	SIGMOD	5.4823129e-05
8,035	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.4025473e-05
8,421	Sampling Methods for Inner Product Sketching	2024	VLDB	5.3350162e-05
8,477	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.3332727e-05
8,516	Optimistic Data Parallelism for FPGA-Accelerated Sketching	2023	VLDB	5.3250329e-05
8,668	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	5.2918151e-05
8,815	Bias-Aware Sketches	2017	VLDB	5.2708103e-05
8,846	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2649328e-05
9,039	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.2331548e-05
9,890	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.1149505e-05
9,893	Approximate Sketches	2024	SIGMOD	5.1134687e-05
10,507	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	4.9793485e-05
12,005	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9793485e-05
12,349	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	4.9793485e-05
12,899	GS-TMS: A Global Stream-based Threat Monitor System	2008	VLDB	4.9793485e-05
12,913	Public Health for the Internet (phi): Towards A New Grand Challenge for Information Management	2007	CIDR	4.9793485e-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.00035978046
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023435436
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020519525
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016296423
734	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014374443
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
850	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013488409
1,434	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010665845
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
5,654	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0507163e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	565	Distributed Top-K Monitoring	2003	SIGMOD
2	14,151	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2006	VLDB
3	734	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
4	12,446	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB
5	7,870	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
7	7,431	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,349	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
10	7,916	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB