Approximate Query Processing Using Wavelets

Summary: Introduces multi-dimensional wavelet coefficient synopses for general-purpose AQP on high-dimensional data. Queries run on wavelet-coefficient synopses, delivering approximate results with final expansion postponed; outperforms sampling and histograms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8639
Venue: VLDB
Year: 2000
Pagerank: 0.00024057494
Overall Rank: 405 | 97.19%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,340	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	4.3556432e-05
9,621	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	4.3167167e-05
9,782	A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays	2010	VLDB	4.2856106e-05
9,869	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	4.2675361e-05
9,950	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	4.2421586e-05
10,187	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	4.1945683e-05
10,216	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	4.1945683e-05
10,399	U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation	2025	SIGMOD	4.1945683e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
11,194	A Step Toward Deep Online Aggregation	2023	SIGMOD	4.1945683e-05
11,539	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.1945683e-05
12,338	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1945683e-05
12,342	Enabling epsilon-Approximate Querying in Sensor Networks	2009	VLDB	4.1945683e-05
12,610	AIMS: An Immersidata Management System	2003	CIDR	4.1945683e-05
12,643	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
1,887	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	0.00010204659
2,661	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	8.3575285e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,260	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00012993347
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
5,579	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4245689e-05
4,698	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9887317e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026702512
5,783	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.3289633e-05
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00012191684
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302