Computing unrestricted synopses under maximum error bound

Chaoyi Pang, Qing Zhang, Xiaofang Zhou, David Hansen, Sen Wang, Anthony Maeder

    Research output: Contribution to journalArticlepeer-review

    15 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)1-42
    Number of pages42
    JournalAlgorithmica
    Volume65
    Issue number1
    DOIs
    Publication statusPublished - Jan 2013

    Keywords

    • Approximate query processing
    • Approximation algorithm
    • Data compression
    • Data synopses
    • Haar wavelets

    Fingerprint Dive into the research topics of 'Computing unrestricted synopses under maximum error bound'. Together they form a unique fingerprint.

    Cite this