Streaming algorithms for data in motion

M. Hoffmann; S. Muthukrishnan; Rajeev Raman

doi:10.1007/978-3-540-74450-4_27

Streaming algorithms for data in motion

M. Hoffmann, S. Muthukrishnan, Rajeev Raman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language	English (US)
Title of host publication	Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers
Publisher	Springer Verlag
Pages	294-304
Number of pages	11
ISBN (Print)	9783540744498
DOIs	https://doi.org/10.1007/978-3-540-74450-4_27
State	Published - 2007
Event	1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007 - Hangzhou, China Duration: Apr 7 2007 → Apr 9 2007

Publication series

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

Conference

Conference	1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007
Country/Territory	China
City	Hangzhou
Period	4/7/07 → 4/9/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-74450-4_27

Cite this

Hoffmann, M., Muthukrishnan, S., & Raman, R. (2007). Streaming algorithms for data in motion. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers (pp. 294-304). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4614 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-74450-4_27

Streaming algorithms for data in motion. / Hoffmann, M.; Muthukrishnan, S.; Raman, Rajeev.
Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers. Springer Verlag, 2007. p. 294-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4614 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hoffmann, M, Muthukrishnan, S & Raman, R 2007, Streaming algorithms for data in motion. in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4614 LNCS, Springer Verlag, pp. 294-304, 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007, Hangzhou, China, 4/7/07. https://doi.org/10.1007/978-3-540-74450-4_27

Hoffmann M, Muthukrishnan S, Raman R. Streaming algorithms for data in motion. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers. Springer Verlag. 2007. p. 294-304. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-74450-4_27

Hoffmann, M. ; Muthukrishnan, S. ; Raman, Rajeev. / Streaming algorithms for data in motion. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers. Springer Verlag, 2007. pp. 294-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9a18f380af7d4728a2601e7ca308865b,

title = "Streaming algorithms for data in motion",

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

author = "M. Hoffmann and S. Muthukrishnan and Rajeev Raman",

note = "Funding Information: ACKNOWLEDGEMENTS The authors gratefully acknowledge the Groupe de Recherche CNRS 1165 for its support and the European Community for the TMR scholarship of one of us (D.W.).; 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007 ; Conference date: 07-04-2007 Through 09-04-2007",

year = "2007",

doi = "10.1007/978-3-540-74450-4_27",

language = "English (US)",

isbn = "9783540744498",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "294--304",

booktitle = "Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers",

}

TY - GEN

T1 - Streaming algorithms for data in motion

AU - Hoffmann, M.

AU - Muthukrishnan, S.

AU - Raman, Rajeev

N1 - Funding Information: ACKNOWLEDGEMENTS The authors gratefully acknowledge the Groupe de Recherche CNRS 1165 for its support and the European Community for the TMR scholarship of one of us (D.W.).

PY - 2007

Y1 - 2007

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

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

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

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

U2 - 10.1007/978-3-540-74450-4_27

DO - 10.1007/978-3-540-74450-4_27

M3 - Conference contribution

AN - SCOPUS:38049015031

SN - 9783540744498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 294

EP - 304

BT - Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers

PB - Springer Verlag

T2 - 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007

Y2 - 7 April 2007 through 9 April 2007

ER -

Streaming algorithms for data in motion

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this