One-pass wavelet decompositions of data streams

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

Research output: Contribution to journalArticle

Abstract

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
Volume15
Issue number3
DOIs
StatePublished - May 1 2003
Externally publishedYes

Keywords

  • Approximate queries
  • Data streams
  • Randomized algorithms
  • Wavelets

ASJC Scopus subject areas

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

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

  • Cite this

    Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2003). One-pass wavelet decompositions of data streams. IEEE Transactions on Knowledge and Data Engineering, 15(3), 541-554. https://doi.org/10.1109/TKDE.2003.1198389