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.0002130211
Overall Rank
312 | 97.91%
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.00052097907
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030586757
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001831946
463 Counting Triangles in Data Streams 2006 PODS 0.00017799662
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016288995
679 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00014831743
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
843 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013534623
863 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013390792
1,067 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012187242
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001168187
1,320 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011040663
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010676907
1,667 Characterizing Memory Requirements for Queries over Continuous Data Streams 2002 PODS 9.9335373e-05
2,210 Multi-Dimensional Regression Analysis of Time-Series Data Streams 2002 VLDB 8.8340718e-05
2,261 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.7313225e-05
2,360 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5774153e-05
2,465 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.4213787e-05
2,664 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 8.1532061e-05
2,738 Sketching Probabilistic Data Streams 2007 SIGMOD 8.0692701e-05
2,876 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 7.9156746e-05
3,082 Persistent Data Sketching 2015 SIGMOD 7.6626082e-05
3,096 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6497893e-05
3,212 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5324957e-05
4,377 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6269629e-05
4,418 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6058591e-05
4,592 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.5109054e-05
4,664 Time Series Compressibility and Privacy 2007 VLDB 6.4782305e-05
4,866 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.3733138e-05
4,933 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3454089e-05
5,047 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.2972183e-05
5,273 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.1986796e-05
5,397 Adaptive, Hands-Off Stream Mining 2003 VLDB 6.1479216e-05
5,503 Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams 2016 SIGMOD 6.1005523e-05
5,623 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0586084e-05
5,653 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.048773e-05
6,324 Subsequence Matching on Structured Time Series Data 2005 SIGMOD 5.8122392e-05
7,572 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.492682e-05
9,676 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.142891e-05
10,318 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0363234e-05
12,768 Parsimonious Linear Fingerprinting for Time Series 2010 VLDB 4.9769913e-05
12,828 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.9769913e-05
13,020 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.9769913e-05
13,099 AIMS: An Immersidata Management System 2003 CIDR 4.9769913e-05
13,132 How to Evaluate Multiple Range-Sum Queries Progressively 2002 PODS 4.9769913e-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
83 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00035962466
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024210103
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021376597
429 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018445263
450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018025134
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017955913
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016288241
588 Computing Iceberg Queries Efficiently 1998 VLDB 0.00015899635
643 Evaluating Top-k Selection Queries 1999 VLDB 0.0001521012
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012588952
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
2,537 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.3249336e-05
3,303 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4400795e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 14,184 Offline and Data Stream algorithms for efficient computation of synopsis structures 2005 VLDB
2 169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
3 1,067 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD
5 5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD
6 5,623 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,272 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB
9 3,303 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
10 309 Approximate Query Processing Using Wavelets 2000 VLDB