DBScholar

Back to papers

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

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 50 of 66 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052121228
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.0002867034
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.0002211981
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021311793
318 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021167555
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
512 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017050173
563 Graph Summarization with Bounded Error 2008 SIGMOD 0.00016327158
701 Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data 2001 SIGMOD 0.00014680907
750 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014265196
842 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013540697
850 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013488409
931 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013011667
1,082 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012122749
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00011686985
1,661 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9535453e-05
1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.9088372e-05
2,000 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2112617e-05
2,359 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5813849e-05
2,396 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.5278724e-05
2,415 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.4985276e-05
2,489 FAS - a Freshness-Sensitive Coordination Middleware for a Cluster of OLAP Components 2002 VLDB 8.3968758e-05
2,655 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1706092e-05
2,717 Partial Results in Database Systems 2014 SIGMOD 8.0980367e-05
2,776 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0309448e-05
3,092 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.6563998e-05
3,246 Approximate XML Query Answers 2004 SIGMOD 7.4946879e-05
3,851 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9785886e-05
3,988 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.871854e-05
4,272 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.6925708e-05
4,416 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6089486e-05
4,590 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.5139479e-05
4,796 Rethinking Data Management for Storage-centric Sensor Networks 2007 CIDR 6.4114857e-05
4,932 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3483816e-05
5,021 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3106761e-05
5,044 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.30014e-05
5,454 SeeDB: Visualizing Database Queries Efficiently 2014 VLDB 6.1240062e-05
5,622 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0614658e-05
5,652 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0515502e-05
5,655 Scalable Ranked Publish/Subscribe 2008 VLDB 6.0501178e-05
5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9961546e-05
5,840 Pre-training Summarization Models of Structured Datasets for Cardinality Estimation 2022 VLDB 5.9737703e-05
6,134 OM3: An Ordered Multi-level Min-Max Representation for Interactive Progressive Visualization of Time Series 2023 SIGMOD 5.8766115e-05
6,682 Hierarchical Residual Encoding for Multiresolution Time Series Compression 2023 SIGMOD 5.7093663e-05
6,746 Progressive Indexes: Indexing for Interactive Data Analysis 2019 VLDB 5.6907873e-05
7,247 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.5748328e-05
8,416 U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation 2025 SIGMOD 5.3350162e-05
8,490 THEMIS: Fairness in Federated Stream Processing under Overload 2016 SIGMOD 5.3315439e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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