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: 8732
Venue: VLDB
Year: 2001
Pagerank: 0.00026702512
Overall Rank: 344 | 97.61%
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.00072723062
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
475	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00022303253
745	Distributed Top-K Monitoring	2003	SIGMOD	0.00017330487
785	StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time	2002	VLDB	0.00016664156
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
1,392	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012229045
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00012191684
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
1,717	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010793312
1,904	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010154528
2,404	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8837279e-05
2,448	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	8.8032353e-05
2,629	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4160309e-05
2,759	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1636123e-05
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
3,050	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.6512619e-05
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05
3,544	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	6.9898874e-05
3,614	Persistent Data Sketching	2015	SIGMOD	6.9147318e-05
3,719	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8204683e-05
3,783	Time Series Compressibility and Privacy	2007	VLDB	6.7714995e-05
3,991	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.5553055e-05
4,382	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.2386853e-05
4,649	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.0236001e-05
4,698	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9887317e-05
5,310	Online Event-driven Subsequence Matching over Financial Data Streams	2004	SIGMOD	5.5753015e-05
5,481	Adaptive, Hands-Off Stream Mining	2003	VLDB	5.4843702e-05
5,496	Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams	2016	SIGMOD	5.4757316e-05
5,535	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	5.4539235e-05
5,579	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4245689e-05
5,903	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	5.2791351e-05
6,405	Subsequence Matching on Structured Time Series Data	2005	SIGMOD	5.0784401e-05
8,697	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.4657888e-05
9,340	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	4.3556432e-05
9,950	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	4.2421586e-05
12,276	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	4.1945683e-05
12,338	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1945683e-05
12,531	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1945683e-05
12,610	AIMS: An Immersidata Management System	2003	CIDR	4.1945683e-05
12,643	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.1945683e-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.00044744986
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
597	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019475592
619	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00019066583
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
1,127	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00013819179
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
2,835	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0448428e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,667	Offline and Data Stream algorithms for efficient computation of synopsis structures	2005	VLDB	-
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
1,392	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012229045
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00012191684
5,783	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.3289633e-05
5,579	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4245689e-05
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
4,659	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.0160083e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494