DBScholar

Back to papers

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

Summary: Introduces one-pass, small-space sketches that capture wavelet-like linear projections over massive streams. Supports approximate point and range-sum queries with low per-item processing cost and experimentally validated accuracy. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hf70f6ac7622c979b
Venue
VLDB
Year
2001
Pagerank
0.00021238056
Overall Rank
316 | 97.89%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gilbert_vldb01,
        title = {{Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries}},
        author = {Gilbert, Anna C. and Kotidis, Yannis and Muthukrishnan, S. and Strauss, Martin J.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00051942573
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030503973
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00018277436
465 Counting Triangles in Data Streams 2006 PODS 0.00017754185
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016238411
682 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00014783422
745 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014267268
844 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013498392
861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013374869
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001165008
1,329 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011013041
1,439 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010641857
1,674 Characterizing Memory Requirements for Queries over Continuous Data Streams 2002 PODS 9.9008287e-05
2,222 Multi-Dimensional Regression Analysis of Time-Series Data Streams 2002 VLDB 8.8048988e-05
2,274 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.7041791e-05
2,364 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5549846e-05
2,472 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.3988741e-05
2,667 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 8.1324472e-05
2,749 Sketching Probabilistic Data Streams 2007 SIGMOD 8.0426455e-05
2,887 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 7.8903242e-05
3,090 Persistent Data Sketching 2015 SIGMOD 7.6420011e-05
3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6394636e-05
3,219 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.50928e-05
4,401 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6051378e-05
4,438 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.5840202e-05
4,607 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.4894359e-05
4,678 Time Series Compressibility and Privacy 2007 VLDB 6.4568192e-05
4,888 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.3522397e-05
4,962 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3244317e-05
5,056 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.282339e-05
5,292 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.1783225e-05
5,414 Adaptive, Hands-Off Stream Mining 2003 VLDB 6.1275934e-05
5,525 Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams 2016 SIGMOD 6.0809613e-05
5,636 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0385837e-05
5,664 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0293278e-05
6,335 Subsequence Matching on Structured Time Series Data 2005 SIGMOD 5.7930204e-05
7,587 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.4745198e-05
9,705 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.1258854e-05
10,346 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0197268e-05
12,811 Parsimonious Linear Fingerprinting for Time Series 2010 VLDB 4.9605343e-05
12,871 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.9605343e-05
13,062 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.9605343e-05
13,140 AIMS: An Immersidata Management System 2003 CIDR 4.9605343e-05
13,173 How to Evaluate Multiple Range-Sum Queries Progressively 2002 PODS 4.9605343e-05
Previous Page 1 / 1 Next

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
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036097627
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027063233
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024136952
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023327437
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
442 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018182341
457 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017915659
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016236872
591 Computing Iceberg Queries Efficiently 1998 VLDB 0.00015853273
647 Evaluating Top-k Selection Queries 1999 VLDB 0.00015165562
1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012551491
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
2,544 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.2988657e-05
3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4165176e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 14,224 Offline and Data Stream algorithms for efficient computation of synopsis structures 2005 VLDB
2 171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
3 1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD
5 5,800 Extended Wavelets for Multiple Measures 2003 SIGMOD
6 5,636 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB
7 222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD
8 4,290 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB
9 3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
10 311 Approximate Query Processing Using Wavelets 2000 VLDB