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
8639
Venue
VLDB
Year
2000
Pagerank
0.0001381102
Overall Rank
1,126 | 92.18%
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.00072660894
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
849 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015919478
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,257 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013002384
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001219602
2,369 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9462051e-05
2,818 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.0673424e-05
3,989 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5545373e-05
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
4,696 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9843254e-05
5,543 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4486922e-05
5,588 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4193309e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
5,908 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2731311e-05
7,460 Compact Histograms for Hierarchical Identifiers 2006 VLDB 4.7198214e-05
11,759 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.1905499e-05
12,346 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.1905499e-05
12,619 AIMS: An Immersidata Management System 2003 CIDR 4.1905499e-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.00080571183
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266
275 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029381206
527 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00020862475
1,240 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013090678
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
275 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029381206
2,752 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1723418e-05
9,345 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 4.351469e-05
4,696 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9843254e-05
849 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015919478
4,656 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.0101164e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001219602
5,908 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2731311e-05
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841