Dynamic Maintenance of Wavelet-Based Histograms

摘要: In this paper, we introduce an e cient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that provide more accurate selectivity estimation than traditional histograms, such as equi-depth histograms. But since are built by a nontrivial mathematical procedure, namely, wavelet transform decomposition, it is hard to maintain accuracy histogram when underlying data distribution changes over time. particular, simple techniques, split and merge, which works well updating xed set coe cients, not suitable here. We propose novel approach based upon probabilistic counting sampling waveletbased with very little online time space costs. The our robust changing distributions, get considerable improvement previous methods A nice feature can be extended naturally multidimensional while less prohibitively expensive build maintain.