  In this paper we consider the wavelet synopsis construction problem without
the restriction that we only choose a subset of coefficients of the original
data. We provide the first near optimal algorithm. We arrive at the above
algorithm by considering space efficient algorithms for the restricted version
of the problem. In this context we improve previous algorithms by almost a
linear factor and reduce the required space to almost linear. Our techniques
also extend to histogram construction, and improve the space-running time
tradeoffs for V-Opt and range query histograms. We believe the idea applies to
a broad range of dynamic programs and demonstrate it by showing improvements in
a knapsack-like setting seen in construction of Extended Wavelets.
