Wavelet Synopses with Predefined Error Bounds: Windfalls of Duality

Speaker: Panagiotis Karras

Abstract

To date, research on wavelet-based synopsis construction has primarily focused on the space-bounded problem: given a data set and a space bound B, construct a B-term representation in the wavelet domain that estimates the data with as good quality as possible, according to a specified error metric. Surprisingly, no adequate attention has been given to the complementary problem: given a bound e for the specified error metric, construct a representation in the wavelet domain that satisfies this bound and occupies as little space as possible. In this talk we expand the toolbox of wavelet synopsis algorithms into this error-bounded problem, devising an unrestricted DP algorithm that achieves the optimal amount of space for a given maximum error bound under well-defined conditions. We then focus on the computational relationship between this pair of problems: we demonstrate that the space-bounded problem can be most efficiently solved indirectly, via the error-bounded, and we prove that this computational benefit increases with dimensionality. In addition, we design one-pass unrestricted greedy heuristics for both problems that operate under tight space constraints.