One-pass wavelet decompositions of data streams
Authors:
- 13 May 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 15 (3) , 541-554
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.Keywords
This publication has 33 references indexed in Scilit:
- Fjording the stream: an architecture for queries over streaming sensor data2003
- Clustering data streams2002
- Stable distributions, pseudorandom generators, embeddings and data stream computation2002
- Processing complex aggregate queries over data streams2002
- Fast, small-space algorithms for approximate histogram maintenance2002
- Near-optimal sparse fourier representations via sampling2002
- How to Summarize the Universe2002
- Optimal and approximate computation of summary statistics for range aggregates2001
- Multi-dimensional selectivity estimation using compressed histogram information1999
- New sampling-based summary statistics for improving approximate query answers1998