One-pass wavelet decompositions of data streams

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss

    Research output: Contribution to journalArticlepeer-review


    We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of the underlying data. We present general "sketch"-based methods for capturing various linear projections and use them to provide pointwise and rangesum estimation of data streams. These methods use small amounts of space and per-item time while streaming through the data and provide accurate representation as our experiments with real data streams show.

    Original languageEnglish (US)
    Pages (from-to)541-554
    Number of pages14
    JournalIEEE Transactions on Knowledge and Data Engineering
    Issue number3
    StatePublished - May 2003


    • Approximate queries
    • Data streams
    • Randomized algorithms
    • Wavelets

    ASJC Scopus subject areas

    • Information Systems
    • Computer Science Applications
    • Computational Theory and Mathematics


    Dive into the research topics of 'One-pass wavelet decompositions of data streams'. Together they form a unique fingerprint.

    Cite this