One-pass wavelet decompositions of data streams

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2003-05, Vol.15 (3), p.541-554
Main Authors: Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.J.
Format: Article
Language:English
Subjects:
Approximation
Computation
Data mining
Data processing
Data structures
Decomposition
History
Monitoring
Projection
Representations
Streams
Switches
Telecommunication switching
Telecommunication traffic
Telephony
Wavelet
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2003.1198389