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

257 Scopus citations

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

All Science Journal Classification (ASJC) codes

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

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.