Database Paper Browser

Back to papers

Dynamic Maintenance of Wavelet-Based Histograms

Summary: Dynamic maintenance of wavelet-based histograms via probabilistic counting and sampling enables fast online updates. The method preserves accuracy under distribution drift and scales to multidimensional histograms, outperforming standard update methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8638
Venue
VLDB
Year
2000
Pagerank
0.00013819179
Overall Rank
1,127 | 92.17%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072723062
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026702512
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
852 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015941524
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,260 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012993347
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00012191684
2,377 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9402115e-05
2,814 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.0749691e-05
3,991 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5553055e-05
4,438 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1898903e-05
4,698 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9887317e-05
5,535 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4539235e-05
5,579 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4245689e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
5,903 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2791351e-05
7,459 Compact Histograms for Hierarchical Identifiers 2006 VLDB 4.7243492e-05
11,751 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.1945683e-05
12,338 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.1945683e-05
12,610 AIMS: An Immersidata Management System 2003 CIDR 4.1945683e-05
Previous Page 1 / 1 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
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
273 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029390945
275 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029364901
529 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00020828852
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
273 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029390945
2,748 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1785955e-05
9,340 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 4.3556432e-05
4,698 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9887317e-05
852 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015941524
4,659 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.0160083e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00012191684
5,903 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2791351e-05
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302