Optimal workload-based weighted wavelet synopses


          

刊名：Theoretical Computer Science
作者：Yossi Matias
Daniel Urieli
刊号：738LB004
ISSN：0304-3975
出版年：2007
年卷期：2007, vol.371, no.3
页码：227-246
总页数：20
分类号：TP30; O1
关键词：Approximation theory；Massive data sets；Workload-based；Wavelet synopses；Weighted wavelets；Weighted inner product
参考中译：
语种：eng
文摘：In recent years wavelets were shown to be effective data synopses. We are concerned with the problem of finding efficiently wavelet synopses for massive data sets, in situations where information about query workload is available. We present linear time, I/O optimal algorithms for building optimal workload-based wavelet synopses for point queries. The synopses are based on a novel construction of weighted inner products and use weighted wavelets that are adapted to those products. The synopses are optimal in the sense that the subset of retained coefficients is the best possible for the bases in use with respect to either the mean-squared absolute or relative errors. For the latter, this is the first optimal wavelet synopsis even for the regular, non-workload-based case. Experimental results demonstrate the advantage obtained by the new optimal wavelet synopses.



©2016机械工业出版社（机械工业信息研究院） 京ICP备05055788号-35