Streaming algorithms for data in motion

M. Hoffmann, S. Muthukrishnan, Rajeev Raman

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

2 Scopus citations

Abstract

We propose two new data stream models: the reset model and the delta model, motivated by applications to databases, and to tracking the location of spatial points. We present algorithms for several problems that fit within the stream constraint of polylogarithmic space and time. These include tracking the "extent" of the points and Lp sampling.

Original languageEnglish (US)
Title of host publicationCombinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers
PublisherSpringer Verlag
Pages294-304
Number of pages11
ISBN (Print)9783540744498
DOIs
StatePublished - 2007
Event1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007 - Hangzhou, China
Duration: Apr 7 2007Apr 9 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4614 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007
Country/TerritoryChina
CityHangzhou
Period4/7/074/9/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Streaming algorithms for data in motion'. Together they form a unique fingerprint.

Cite this