Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries

Summary: Wavelet-inspired, one-pass sketches for streaming aggregates. Develops generic sketch-based linear projections to enable accurate pointwise and range-sum estimates under tiny space, with constant per-item processing, validated on real data streams. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8733
Venue: VLDB
Year: 2001
Pagerank: 0.00026698826
Overall Rank: 344 | 97.62%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
481	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.000221538
743	Distributed Top-K Monitoring	2003	SIGMOD	0.00017318557
783	StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time	2002	VLDB	0.00016648503
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001219602
1,586	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011245213
1,712	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010786152
1,904	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010144623
2,403	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8738166e-05
2,448	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	8.7935134e-05
2,635	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4081184e-05
2,766	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1559016e-05
2,934	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8628636e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,123	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5270618e-05
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05
3,545	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	6.9831585e-05
3,618	Persistent Data Sketching	2015	SIGMOD	6.9080647e-05
3,720	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8139746e-05
3,788	Time Series Compressibility and Privacy	2007	VLDB	6.7624343e-05
3,989	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.5545373e-05
4,379	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.2326895e-05
4,647	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.01732e-05
4,696	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9843254e-05
5,314	Online Event-driven Subsequence Matching over Financial Data Streams	2004	SIGMOD	5.5702825e-05
5,489	Adaptive, Hands-Off Stream Mining	2003	VLDB	5.4790681e-05
5,510	Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams	2016	SIGMOD	5.4704702e-05
5,543	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	5.4486922e-05
5,588	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4193309e-05
5,908	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	5.2731311e-05
6,401	Subsequence Matching on Structured Time Series Data	2005	SIGMOD	5.0735622e-05
8,695	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.461508e-05
9,345	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	4.351469e-05
9,946	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	4.240067e-05
12,284	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	4.1905499e-05
12,346	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1905499e-05
12,540	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1905499e-05
12,619	AIMS: An Immersidata Management System	2003	CIDR	4.1905499e-05
12,652	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059
527	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020862475
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
598	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019431661
617	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00019048986
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
1,126	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.0001381102
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
2,840	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0417349e-05
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,681	Offline and Data Stream algorithms for efficient computation of synopsis structures	2005	VLDB	-
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001219602
5,794	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.323907e-05
5,588	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4193309e-05
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
4,656	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.0101164e-05
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968