On the Optimality of the Greedy Heuristic in Wavelet Synopses for Range Queries
Yossi Matias, Daniel Urieli · 2005
In recent years wavelet based synopses were shown to be efiective for approximate queries in database systems. The simplest wavelet synopses are constructed by computing the Haar transform over a vector consisting of either the raw-data or the preflx-sums of the data, and using a greedy-heuristic to select the wavelet coe‐cients that are kept in the synopsis. The greedy-heuristic is known to be optimal for point queries w.r.t. the mean-squared-error, but no similar optimality result was known for range-sum queries, for which the efiectiveness of such synopses was only shown experimentally. The optimality of the greedy-heuristic for the case of point queries is due to the Haar basis being orthonormal for this case, which allows using the Parseval-based thresholding. Thus, the main technical question we are concerned with in this paper is whether the Haar basis is orthonormal for the case of range-sum queries. We show that it is not orthogonal for the case of range-sum queries over the raw data, and that it is orthonormal for the case of preflx-sums. Consequently, we show that a slight variation of the greedy-heuristic over the preflx-sums of the data is an optimal thresholding w.r.t. the mean-squared-error. As a result, we obtain the flrst linear time construction of a provably optimal wavelet synopsis for range-sum queries. The crux of our proof is based on a novel construction of inner products, that deflne the error measured over range-sum queries.