Title: Have epsilons helped you lately? Algorithmic impact on Histogram & Wavelet construction problems
Speaker: Sudipto Guha, University of Pennsylvania
Date: May 3, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Histograms, Wavelets and related synopsis structures have been successful in a wide variety of popular database applications including approximate querying, similarity searching and data mining. Histograms were a few of the earliest synopsis structures proposed and continue to be popular tools. These problems pose a wealth of well-motivated optimization problems.
At the same time the synopsis construction problems are most important when resources such as space, random access ( and obviously time) are scarce. Approximation algorithms are a natural way forward in such a context. We will review some of the recent developments in this area. Interestingly the study of approximation algorithms lead us to techniques that allow us to develop space efficient optimal algorithms for a wide variety of these problems.
In this talk we will focus on space efficient synopsis construction and approximations for the wavelet optimization problem. In case of the former we improve the space bound of almost all known algorithms for wavelet and histogram reconstruction problems. For the latter, we provide the first approximation scheme for wavelet reconstruction problem under non-L2 error measures, as well as the first data stream algorithms for such.