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.00021384073
Overall Rank: 309 | 97.93%
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,659	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.2930951e-05
8,846	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2649328e-05
9,387	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1868213e-05
9,575	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.1571823e-05
9,669	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	5.1453267e-05
10,117	A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays	2010	VLDB	5.0789354e-05
10,205	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0603873e-05
10,316	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0377739e-05
10,663	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	4.9793485e-05
10,691	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	4.9793485e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05
12,039	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.9793485e-05
12,822	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.9793485e-05
12,826	Enabling epsilon-Approximate Querying in Sensor Networks	2009	VLDB	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

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.00076195956
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
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
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
1,764	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.6965217e-05
3,332	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	7.4163853e-05

Semantically Similar Papers

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