Approximate Query Processing Using Wavelets

Summary: Uses multidimensional wavelet-coefficient synopses for general-purpose, high-dimensional approximate query processing. Novel algorithms execute arbitrarily complex relational queries directly in coefficient space, outperforming sampling and histograms while enabling rapid exploratory analytics. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h376c60cb96528cc2
Venue: VLDB
Year: 2000
Pagerank: 0.00021315058
Overall Rank: 311 | 97.92%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Kaushik Chakrabarti (University of Illinois Urbana-Champaign)
2. Minos Garofalakis (AT&T)
3. Rajeev Rastogi (AT&T)
4. Kyuseok Shim (Advanced Information Technology Research Center at Korea Advanced Institute of Science and Technology; Korea Advanced Institute of Science and Technology)

BibTeX Citation

@article{chakrabarti_vldb00,
        title = {{Approximate Query Processing Using Wavelets}},
        author = {Chakrabarti, Kaushik and Garofalakis, Minos and Rastogi, Rajeev and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {111--122},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,685	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.2730954e-05
8,870	Data Driven Approximation with Bounded Resources	2017	VLDB	5.246202e-05
9,422	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1672232e-05
9,608	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.1376962e-05
9,705	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	5.1258854e-05
10,158	A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays	2010	VLDB	5.0597449e-05
10,249	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0412674e-05
10,346	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0197268e-05
10,735	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	4.9605343e-05
10,762	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	4.9605343e-05
11,353	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9605343e-05
12,089	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.9605343e-05
12,871	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.9605343e-05
12,875	Enabling epsilon-Approximate Querying in Sensor Networks	2009	VLDB	4.9605343e-05
13,140	AIMS: An Immersidata Management System	2003	CIDR	4.9605343e-05
13,173	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.9605343e-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
9	Online Aggregation	1997	SIGMOD	0.00076079812
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024136952
450	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.0001806593
1,779	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.6641413e-05
3,341	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	7.3884891e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	935	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD
2	3,168	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
3	5,636	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB
4	4,438	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS
5	3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
6	316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB
7	5,800	Extended Wavelets for Multiple Measures	2003	SIGMOD
8	1,174	Wavelet Synopses with Error Guarantees	2002	SIGMOD
9	222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
10	171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD