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: 9465
Venue: VLDB
Year: 2005
Pagerank: 0.00012440928
Overall Rank: 1,045 | 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,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.0001080304
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
2,340	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.7246796e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
4,989	Shape Sensitive Geometric Monitoring	2008	PODS	6.4106441e-05
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
5,998	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	6.0142553e-05
6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.7985588e-05
6,871	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.7496345e-05
7,069	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.7117595e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-05
7,479	Distributed Online Tracking	2015	SIGMOD	5.6081446e-05
7,747	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.5529458e-05
8,252	Sampling Methods for Inner Product Sketching	2024	VLDB	5.4574671e-05
8,310	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.4556836e-05
8,356	Optimistic Data Parallelism for FPGA-Accelerated Sketching	2023	VLDB	5.4450094e-05
8,501	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	5.4132745e-05
8,653	Bias-Aware Sketches	2017	VLDB	5.3914428e-05
8,701	Data Driven Approximation with Bounded Resources	2017	VLDB	5.3828806e-05
8,878	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.3532614e-05
9,027	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.3293224e-05
9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.2323504e-05
9,724	Approximate Sketches	2024	SIGMOD	5.2308295e-05
10,295	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	5.093636e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-05
12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	5.093636e-05
12,609	GS-TMS: A Global Stream-based Threat Monitor System	2008	VLDB	5.093636e-05
12,623	Public Health for the Internet (phi): Towards A New Grand Challenge for Information Management	2007	CIDR	5.093636e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014627248
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.1895841e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	550	Distributed Top-K Monitoring	2003	SIGMOD
2	13,840	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2006	VLDB
3	722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
4	12,155	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB
5	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
7	7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD
8	2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
9	12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
10	7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB