Surfing wavelets on streams

One-pass summaries for approximate aggregate queries

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

253 Citations (Scopus)

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 of the data 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)
Title of host publicationVLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases
EditorsPeter M. G. Apers, Paolo Atzeni, Richard T. Snodgrass, Stefano Ceri, Kotagiri Ramamohanarao, Stefano Paraboschi
PublisherMorgan Kaufmann
Pages79-88
Number of pages10
ISBN (Electronic)1558608044, 9781558608047
StatePublished - Jan 1 2001
Event27th International Conference on Very Large Data Bases, VLDB 2001 - Roma, Italy
Duration: Sep 11 2001Sep 14 2001

Publication series

NameVLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases

Other

Other27th International Conference on Very Large Data Bases, VLDB 2001
CountryItaly
CityRoma
Period9/11/019/14/01

Fingerprint

Experiments
Wavelets
Data streams
Query
Experiment
Approximation

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Science Applications

Cite this

Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001). Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In P. M. G. Apers, P. Atzeni, R. T. Snodgrass, S. Ceri, K. Ramamohanarao, & S. Paraboschi (Eds.), VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases (pp. 79-88). (VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases). Morgan Kaufmann.
Gilbert, Anna C. ; Kotidis, Yannis ; Muthukrishnan, Shan ; Strauss, Martin J. / Surfing wavelets on streams : One-pass summaries for approximate aggregate queries. VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases. editor / Peter M. G. Apers ; Paolo Atzeni ; Richard T. Snodgrass ; Stefano Ceri ; Kotagiri Ramamohanarao ; Stefano Paraboschi. Morgan Kaufmann, 2001. pp. 79-88 (VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases).
@inproceedings{e742d57c61da4b948078231c6608a7cc,
title = "Surfing wavelets on streams: One-pass summaries for approximate aggregate queries",
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 of the data 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.",
author = "Gilbert, {Anna C.} and Yannis Kotidis and Shan Muthukrishnan and Strauss, {Martin J.}",
year = "2001",
month = "1",
day = "1",
language = "English (US)",
series = "VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases",
publisher = "Morgan Kaufmann",
pages = "79--88",
editor = "Apers, {Peter M. G.} and Paolo Atzeni and Snodgrass, {Richard T.} and Stefano Ceri and Kotagiri Ramamohanarao and Stefano Paraboschi",
booktitle = "VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases",

}

Gilbert, AC, Kotidis, Y, Muthukrishnan, S & Strauss, MJ 2001, Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. in PMG Apers, P Atzeni, RT Snodgrass, S Ceri, K Ramamohanarao & S Paraboschi (eds), VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases. VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases, Morgan Kaufmann, pp. 79-88, 27th International Conference on Very Large Data Bases, VLDB 2001, Roma, Italy, 9/11/01.

Surfing wavelets on streams : One-pass summaries for approximate aggregate queries. / Gilbert, Anna C.; Kotidis, Yannis; Muthukrishnan, Shan; Strauss, Martin J.

VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases. ed. / Peter M. G. Apers; Paolo Atzeni; Richard T. Snodgrass; Stefano Ceri; Kotagiri Ramamohanarao; Stefano Paraboschi. Morgan Kaufmann, 2001. p. 79-88 (VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Surfing wavelets on streams

T2 - One-pass summaries for approximate aggregate queries

AU - Gilbert, Anna C.

AU - Kotidis, Yannis

AU - Muthukrishnan, Shan

AU - Strauss, Martin J.

PY - 2001/1/1

Y1 - 2001/1/1

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 of the data 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 of the data 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.

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

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

M3 - Conference contribution

T3 - VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases

SP - 79

EP - 88

BT - VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases

A2 - Apers, Peter M. G.

A2 - Atzeni, Paolo

A2 - Snodgrass, Richard T.

A2 - Ceri, Stefano

A2 - Ramamohanarao, Kotagiri

A2 - Paraboschi, Stefano

PB - Morgan Kaufmann

ER -

Gilbert AC, Kotidis Y, Muthukrishnan S, Strauss MJ. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Apers PMG, Atzeni P, Snodgrass RT, Ceri S, Ramamohanarao K, Paraboschi S, editors, VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases. Morgan Kaufmann. 2001. p. 79-88. (VLDB 2001 - Proceedings of 27th International Conference on Very Large Data Bases).