Please use this identifier to cite or link to this item:
Title: Multiplicative synopses for relative-error metrics
Authors: Karras, P. 
Issue Date: 2009
Citation: Karras, P. (2009). Multiplicative synopses for relative-error metrics. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT'09 : 756-767. ScholarBank@NUS Repository.
Abstract: Existing hierarchical summarization techniques fail to provide 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 exactly from this additive nature of their representation mechanism. We substitute this additive nature by a multiplicative one. We argue that this is more appropriate for achieving low-relative-error data approximations. We develop an efficient linear-time dynamic programming scheme for one-dimensional multiplicative synopsis construction under general 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. Copyright 2009 ACM.
Source Title: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT'09
ISBN: 9781605584225
DOI: 10.1145/1516360.1516447
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 20, 2019

Page view(s)

checked on Feb 9, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.