Streaming algorithms for data in motion

M. Hoffmann, S. Muthukrishnan, Rajeev Raman

    Research output: Chapter in Book/Report/Conference proceedingConference 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 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

    Conference

    Conference1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007
    CountryChina
    CityHangzhou
    Period4/7/074/9/07

    ASJC Scopus subject areas

    • 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

    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