XWAVE:
Optimal and Approximate Extended Wavelets for Streaming Data
Dr. Kyuseok
Shim
Seoul,
Korea
Date:
Time:
Location: 367 Votey
Abstract
Wavelet synopses have been found
to be of interest in query optimization and approximate query answering.
Recently, extended wavelets were proposed by Deligiannakis and Roussopoulos for datasets
containing multiple measures. Extended wavelets optimize the storage utilization by attempting
to store the same wavelet coefficient across different measures. This reduces
the bookkeeping
overhead and more coefficients can be stored. An optimal algorithm for
minimizing the error in representation and an approximation algorithm
for the complementary problem was provided.
However, both their
algorithms take linear space. Synopsis structures are often used in
environments where space is at a premium and the data arrives
as a continuous stream which is too expensive to store. In this
paper, we give algorithms for extended wavelets which are space
sensitive, i.e., use space which is dependent on the size of the
synopsis (and at most on the logarithm of the total data) and operates in a
streaming fashion. We present better optimal algorithms based on dynamic programming and a near optimal
approximate greedy algorithm. We also demonstrate the performance
benefits of our algorithms compared to previous ones through
experiments on real-life and synthetic data sets.
(This is a joint work with Sudipto Guha and Chulyun
Kim.)