Dynamic Maintenance of Wavelet-Based Histograms

This paper proposes a novel approach based upon probabilistic counting and sampling to maintain waveletbased histograms with very little online time and space costs and is robust to changing data distributions.

Abstract

In this paper, we introduce an efficient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that wavelet-based histograms provide more accurate selectivity estimation than traditional histograms, such as equi-depth histograms. But since wavelet-based histograms are built by a nontrivial mathematical procedure, namely, wavelet transform decomposition, it is hard to maintain the accuracy of the histogram when the underlying data distribution changes over time. In particular, simple techniques, such as split and merge, which works well for equi-depth histograms, and updating a fixed set of wavelet coefficients, are not suitable here. We propose a novel approach based upon probabilistic counting and sampling to maintain waveletbased histograms with very little online time and space costs. The accuracy of our method is robust to changing data distributions, and we get a considerable improvement o...