Wavelet Synopses with Error Guarantees

Summary: Probabilistic Wavelet Synopses, first to provide per-answer error guarantees for wavelet-based data reduction. A probabilistic thresholding scheme assigns each coefficient a retention probability by its reconstruction importance, with optimization algorithms and empirical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3435
Venue: SIGMOD
Year: 2002
Pagerank: 0.00011929041
Overall Rank: 1,156 | 92.08%
DOI: 10.1145/564691.564746

Incoming Non-self Citations Over Time

Authors

1. Minos Garofalakis (AT&T)
2. Phillip B. Gibbons (AT&T; Intel)

BibTeX Citation

@inproceedings{garofalakis_sigmod02,
        title = {{Wavelet Synopses with Error Guarantees}},
        author = {Garofalakis, Minos and Gibbons, Phillip B.},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564746},
        url = {https://dl.acm.org/doi/10.1145/564691.564746},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
3,034	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.8302786e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.8448865e-05
4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.7605683e-05
4,393	Bounded Conjunctive Queries	2014	VLDB	6.7280426e-05
4,629	Time Series Compressibility and Privacy	2007	VLDB	6.5960717e-05
4,882	Managing Massive Time Series Streams with Multi-Scale Compressed Trickles	2009	VLDB	6.4651572e-05
5,272	Adaptive, Hands-Off Stream Mining	2003	VLDB	6.2899363e-05
5,522	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.1871697e-05
5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD	6.1337629e-05
5,792	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	6.0871213e-05
6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.8131331e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-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
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
12,532	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	5.093636e-05
12,803	AIMS: An Immersidata Management System	2003	CIDR	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
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
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
977	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012864017

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
2	5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB
3	11,957	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB
4	311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB
5	10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD
6	12,532	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB
7	5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD
8	307	Approximate Query Processing Using Wavelets	2000	VLDB
9	4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB
10	4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS