One-pass wavelet decompositions of data streams
- 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
- https://doi.org/10.1109/tkde.2003.1198389
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 28 references indexed in Scilit:
- Fjording the stream: an architecture for queries over streaming sensor dataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Clustering data streamsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Stable distributions, pseudorandom generators, embeddings and data stream computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Processing complex aggregate queries over data streamsPublished by Association for Computing Machinery (ACM) ,2002
- Fast, small-space algorithms for approximate histogram maintenancePublished by Association for Computing Machinery (ACM) ,2002
- Near-optimal sparse fourier representations via samplingPublished by Association for Computing Machinery (ACM) ,2002
- How to Summarize the UniversePublished by Elsevier ,2002
- Optimal and approximate computation of summary statistics for range aggregatesPublished by Association for Computing Machinery (ACM) ,2001
- Multi-dimensional selectivity estimation using compressed histogram informationPublished by Association for Computing Machinery (ACM) ,1999
- New sampling-based summary statistics for improving approximate query answersPublished by Association for Computing Machinery (ACM) ,1998