DBScholar

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
hcfa281874f84fea9
Venue
VLDB
Year
2000
Pagerank
0.00012588952
Overall Rank
1,004 | 93.26%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{matias_vldb00,
        title = {{Dynamic Maintenance of Wavelet-Based Histograms}},
        author = {Matias, Yossi and Vitter, Jeffrey Scott and Wang, Min},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {101--112},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030586757
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.0002130211
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
843 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013534623
930 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013009255
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001168187
1,892 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4150583e-05
2,558 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.2968348e-05
4,118 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7927394e-05
4,377 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6269629e-05
4,418 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6058591e-05
5,047 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.2972183e-05
5,623 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0586084e-05
5,653 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.048773e-05
5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9933192e-05
7,517 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.5025167e-05
12,261 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.9769913e-05
12,828 A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees 2009 VLDB 4.9769913e-05
13,099 AIMS: An Immersidata Management System 2003 CIDR 4.9769913e-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
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047864281
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024210103
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023047482
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017955913
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD
2 3,164 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB
3 9,676 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD
4 4,418 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS
5 743 Dynamic Multidimensional Histograms 2002 SIGMOD
6 4,272 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB
7 5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD
8 1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD
9 5,653 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB
10 169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD