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.00021311793
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.00052121228
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030600691
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001832766
462 Counting Triangles in Data Streams 2006 PODS 0.00017807125
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016296423
678 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00014838454
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
842 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013540697
862 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013396995
1,066 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012192801
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00011686985
1,319 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011045888
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010681774
1,666 Characterizing Memory Requirements for Queries over Continuous Data Streams 2002 PODS 9.9382031e-05
2,208 Multi-Dimensional Regression Analysis of Time-Series Data Streams 2002 VLDB 8.8382452e-05
2,260 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.7353589e-05
2,359 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5813849e-05
2,465 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.4253671e-05
2,664 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 8.1569551e-05
2,738 Sketching Probabilistic Data Streams 2007 SIGMOD 8.07308e-05
2,875 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 7.9193665e-05
3,080 Persistent Data Sketching 2015 SIGMOD 7.6662346e-05
3,094 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6533343e-05
3,211 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.536045e-05
4,374 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6300924e-05
4,416 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6089486e-05
4,590 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.5139479e-05
4,662 Time Series Compressibility and Privacy 2007 VLDB 6.4812985e-05
4,865 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.3763323e-05
4,932 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3483816e-05
5,044 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.30014e-05
5,270 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.2013771e-05
5,390 Adaptive, Hands-Off Stream Mining 2003 VLDB 6.1508226e-05
5,499 Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams 2016 SIGMOD 6.1034402e-05
5,622 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0614658e-05
5,652 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0515502e-05
6,320 Subsequence Matching on Structured Time Series Data 2005 SIGMOD 5.8149919e-05
7,566 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.4952834e-05
9,669 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.1453267e-05
10,316 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0377739e-05
12,762 Parsimonious Linear Fingerprinting for Time Series 2010 VLDB 4.9793485e-05
12,822 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.9793485e-05
13,014 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.9793485e-05
13,093 AIMS: An Immersidata Management System 2003 CIDR 4.9793485e-05
13,126 How to Evaluate Multiple Range-Sum Queries Progressively 2002 PODS 4.9793485e-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.00035978046
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028633995
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027134723
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024218831
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023363722
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021384073
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018032912
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017962189
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016295476
588 Computing Iceberg Queries Efficiently 1998 VLDB 0.00015906635
643 Evaluating Top-k Selection Queries 1999 VLDB 0.00015217076
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012594522
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
2,538 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.3284106e-05
3,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4424817e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 14,179 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,066 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD
5 5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD
6 5,622 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,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
10 309 Approximate Query Processing Using Wavelets 2000 VLDB