Sublinear methods for detecting periodic trends in data streams

Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp

    Research output: Chapter in Book/Report/Conference proceedingChapter

    Abstract

    We present sublinear algorithms -algorithms that use significantly less resources than needed to store or process the entire input stream - for discovering representative trends in data streams in the form of periodicities. Our algorithms involve sampling Õ(√n) positions. and thus they scan not the entire data stream but merely a sublinear sample thereof. Alternately, our algorithms may be thought of as working on streaming inputs where each data item is seen once, but we store only a sublinear - Õ(√n) - size sample from which we can identify periodicities. In this work we present a variety of definitions of periodicities of a given stream, present sublinear sampling algorithms for discovering them, and prove that the algorithms meet our specifications and guarantees. No previously known results can provide such guarantees for finding any such periodic trends. We also investigate the relationships between these different definitions of periodicity.

    Original languageEnglish (US)
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    EditorsMartin Farach-Colton
    PublisherSpringer Verlag
    Pages16-28
    Number of pages13
    ISBN (Print)3540212582, 9783540212584
    DOIs
    StatePublished - 2004

    Publication series

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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Sublinear methods for detecting periodic trends in data streams'. Together they form a unique fingerprint.

    Cite this