Computing Unrestricted Synopses Under Maximum Error Bound

Pang, Chaoyi, Zhang, Qing, Zhou, Xiaofang, Hansen, David, Wang, Sen and Maeder, Anthony (2013) Computing Unrestricted Synopses Under Maximum Error Bound. Algorithmica, 65 1: 1-42. doi:10.1007/s00453-011-9571-9

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Pang, Chaoyi
Zhang, Qing
Zhou, Xiaofang
Hansen, David
Wang, Sen
Maeder, Anthony
Title Computing Unrestricted Synopses Under Maximum Error Bound
Journal name Algorithmica   Check publisher's open access policy
ISSN 0178-4617
Publication date 2013-01
Year available 2013
Sub-type Article (original research)
DOI 10.1007/s00453-011-9571-9
Open Access Status
Volume 65
Issue 1
Start page 1
End page 42
Total pages 42
Place of publication Secaucus, NJ., United States
Publisher Springer
Collection year 2014
Language eng
Formatted abstract
Constructing Haar wavelet synopses with guaranteed maximum error on data approximations has many real world applications. In this paper, we take a novel approach towards constructing unrestricted Haar wavelet synopses under maximum error metrics (L ∞). We first provide two linear time (logN)-approximation algorithms which have space complexities of O(logN) and O(N) respectively. These two algorithms have the advantage of being both simple in structure and naturally adaptable for stream data processing. Unlike traditional approaches for synopses construction that rely heavily on examining wavelet coefficients and their summations, the proposed methods are very compact and scalable, and sympathetic for online data processing. We then demonstrate that this technique can be extended to other findings such as Haar+ tree. Extensive experiments indicate that these techniques are highly practical. The proposed algorithms achieve a very attractive tradeoff between efficiency and effectiveness, surpassing contemporary (logN)-approximation algorithms in compressing qualities
Keyword Approximation algorithm
Approximate query processing
Data compression
Data synopses
Haar wavelets
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2014 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 10 Feb 2013, 01:49:03 EST by System User on behalf of School of Information Technol and Elec Engineering