Multiplicative synopses for relative-error metrics

Existing hierarchical summarization techniques fail to pro-vide synopses good in terms of relative-error metrics. This paper introduces multiplicative synopses: a summarization paradigm tailored for effective relative-error summarization. This paradigm is inspired from previous hierarchical index-based summarization schemes, but goes beyond them by altering their underlying data representation mechanism. Existing schemes have decomposed the summarized data based on sums and differences of values, resulting in what we call additive synopses. We argue that the incapacity of these models to handle relative-error metrics stems ex-actly from this additive nature of their representation mech-anism. We substitute this additive nature by a multiplicative one. We argue that this is more appropriate for achiev-ing low-relative-error data approximations. We develop an efficient linear-time dynamic programming scheme for one-dimensional multiplicative synopsis construction under gen-eral relative-error-based metrics, and a special scheme for the case of maximum relative error. We generalize our schemes to higher data dimensionality and we show a surprising additional benefit gained by our special scheme for maximum relative error in this case. In our experimental study, we verify the higher efficacy of our model on relative-error-oriented summarization problems. 1