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: 8830
Venue: VLDB
Year: 2000
Pagerank: 0.00021792475
Overall Rank: 307 | 97.90%
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,701	Data Driven Approximation with Bounded Resources	2017	VLDB	5.3828806e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,392	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.2755515e-05
9,489	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	5.2634238e-05
9,936	A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays	2010	VLDB	5.1955087e-05
10,016	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.1764556e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,476	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	5.093636e-05
10,505	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	5.093636e-05
10,685	U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation	2025	SIGMOD	5.093636e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,736	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	5.093636e-05
12,532	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	5.093636e-05
12,536	Enabling epsilon-Approximate Querying in Sensor Networks	2009	VLDB	5.093636e-05
12,803	AIMS: An Immersidata Management System	2003	CIDR	5.093636e-05
12,836	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	5.093636e-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.00077458002
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
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
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
1,732	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.9065981e-05
3,264	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	7.5841142e-05

Semantically Similar Papers

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