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
8923
Venue
VLDB
Year
2001
Pagerank
0.00021760621
Overall Rank
311 | 97.87%
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.00052982574
122 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00031260115
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
432 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00018572055
458 Counting Triangles in Data Streams 2006 PODS 0.0001810876
550 Distributed Top-K Monitoring 2003 SIGMOD 0.0001663758
668 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00015166017
723 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014620977
817 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013823702
842 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013671191
1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012440928
1,156 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00011929041
1,294 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011291308
1,397 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010906135
1,656 Characterizing Memory Requirements for Queries over Continuous Data Streams 2002 PODS 0.00010097487
2,171 Multi-Dimensional Regression Analysis of Time-Series Data Streams 2002 VLDB 9.0406168e-05
2,218 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.9331834e-05
2,340 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.7246796e-05
2,406 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.6187297e-05
2,697 Sketching Probabilistic Data Streams 2007 SIGMOD 8.2451054e-05
2,698 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 8.2450522e-05
2,808 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 8.1006881e-05
3,023 Persistent Data Sketching 2015 SIGMOD 7.8398269e-05
3,044 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.820774e-05
3,150 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.7055991e-05
4,285 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.7812351e-05
4,325 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.7605683e-05
4,517 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.6481605e-05
4,629 Time Series Compressibility and Privacy 2007 VLDB 6.5960717e-05
4,755 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.5226838e-05
4,819 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.4940349e-05
4,945 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.4321265e-05
5,162 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.339805e-05
5,272 Adaptive, Hands-Off Stream Mining 2003 VLDB 6.2899363e-05
5,372 Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams 2016 SIGMOD 6.2426538e-05
5,490 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.200262e-05
5,522 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.1871697e-05
6,189 Subsequence Matching on Structured Time Series Data 2005 SIGMOD 5.9483531e-05
7,747 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.5529458e-05
9,489 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.2634238e-05
10,094 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.1530576e-05
12,471 Parsimonious Linear Fingerprinting for Time Series 2010 VLDB 5.093636e-05
12,532 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 5.093636e-05
12,724 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 5.093636e-05
12,803 AIMS: An Immersidata Management System 2003 CIDR 5.093636e-05
12,836 How to Evaluate Multiple Range-Sum Queries Progressively 2002 PODS 5.093636e-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.00036378991
149 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00029226907
168 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027541029
213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024723025
235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023783792
307 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021792475
418 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018812821
443 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018373044
448 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00018292618
551 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016635191
577 Computing Iceberg Queries Efficiently 1998 VLDB 0.00016235949
635 Evaluating Top-k Selection Queries 1999 VLDB 0.00015527042
977 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012864017
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
2,493 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.5070756e-05
3,241 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.6057671e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,868 Offline and Data Stream algorithms for efficient computation of synopsis structures 2005 VLDB
2 168 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
3 1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 1,156 Wavelet Synopses with Error Guarantees 2002 SIGMOD
5 5,650 Extended Wavelets for Multiple Measures 2003 SIGMOD
6 5,490 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB
7 213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD
8 4,188 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB
9 3,241 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
10 307 Approximate Query Processing Using Wavelets 2000 VLDB