Please use this identifier to cite or link to this item:
Title: Hierarchical synopses with optimal error guarantees
Authors: Karras, P. 
Mamoulis, N.
Keywords: Approximate query processing
Data synopses
Issue Date: 2008
Citation: Karras, P., Mamoulis, N. (2008). Hierarchical synopses with optimal error guarantees. ACM Transactions on Database Systems 33 (3). ScholarBank@NUS Repository.
Abstract: Hierarchical synopsis structures offer a viable alternative in terms of efficiency and flexibility in relation to traditional summarization techniques such as histograms. Previous research on such structures has mostly focused on a single model, based on the Haar wavelet decomposition. In previous work, we have introduced a more refined, wavelet-inspired hierarchical index structure for synopsis construction: the Haar+ tree. The chief advantages of this structure are twofold. First, it achieves higher synopsis quality at the task of summarizing data sets with sharp discontinuities than state-of-the-art histogram and Haar wavelet techniques. Second, thanks to its search space delimitation capacity, Haar+ synopsis construction operates in time linear in the size of the data set for any monotonic distributive error metric. Contemporaneous research has introduced another hierarchical synopsis structure, the compact hierarchical histogram (CHH). In this article, we elaborate on both these structures. First, we formally prove that the CHH, in its default binary-hierarchy form, is a simplified variant of a Haar+ tree. We then focus on the summarization problem, with both these hierarchical synopsis structures, in which an error guarantee expressed by a maximum-error metric is required. We show that this problem is most efficiently solved through its dual, space-minimization counterpart, which can also achieve optimal quality. In this case, there is a benefit to be gained by specializing the algorithm for each structure; hence, our algorithm for optimal-quality maximum-error CHH requires low polynomial time; on the other hand, optimal-quality Haar+ synopses for maximum-error metrics are constructed in exponential time; hence, we also develop a low-polynomial-time approximation scheme for the maximum-error Haar+ case. Furthermore, we extend our approach for both general-error and maximum-error Haar+ synopses to arbitrary dimensionality. In our experimental study, (i) we confirm the theoretically expected superiority of Haar+ synopses over Haar wavelet methods in both construction time and achieved quality for representative error metrics; (ii) we demonstrate that Haar+ synopses are also constructed faster than optimal plain histograms, and, moreover, achieve higher synopsis quality with highly discontinuous data sets; such an advantage of a hierarchical synopsis structure over a histogram had been intuitively expressed, but never experimentally verified; and (iii) we show that Haar+ synopsis quality supersedes that of a CHH. © 2008 ACM.
Source Title: ACM Transactions on Database Systems
ISSN: 03625915
DOI: 10.1145/1386118.1386124
Appears in Collections:Staff Publications

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


checked on Jan 19, 2022


checked on Jan 19, 2022

Page view(s)

checked on Jan 20, 2022

Google ScholarTM



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