One-pass wavelet decompositions of data streams

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

doi:10.1109/TKDE.2003.1198389

One-pass wavelet decompositions of data streams

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	541-554
Number of pages	14
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	15
Issue number	3
DOIs	https://doi.org/10.1109/TKDE.2003.1198389
State	Published - May 2003

Keywords

Approximate queries
Data streams
Randomized algorithms
Wavelets

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1109/TKDE.2003.1198389

Cite this

@article{75c2c2433c254fb49748c82ab202786e,

title = "One-pass wavelet decompositions of data streams",

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 = "Approximate queries, Data streams, Randomized algorithms, Wavelets",

author = "Gilbert, {Anna C.} and Yannis Kotidis and S. Muthukrishnan and Strauss, {Martin J.}",

year = "2003",

month = may,

doi = "10.1109/TKDE.2003.1198389",

language = "English (US)",

volume = "15",

pages = "541--554",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - One-pass wavelet decompositions of data streams

AU - Gilbert, Anna C.

AU - Kotidis, Yannis

AU - Muthukrishnan, S.

AU - Strauss, Martin J.

PY - 2003/5

Y1 - 2003/5

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

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

KW - Approximate queries

KW - Data streams

KW - Randomized algorithms

KW - Wavelets

UR - http://www.scopus.com/inward/record.url?scp=0037957085&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037957085&partnerID=8YFLogxK

U2 - 10.1109/TKDE.2003.1198389

DO - 10.1109/TKDE.2003.1198389

M3 - Article

AN - SCOPUS:0037957085

SN - 1041-4347

VL - 15

SP - 541

EP - 554

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 3

ER -

One-pass wavelet decompositions of data streams

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this