An improved data stream summary: The count-min sketch and its applications

Graham Cormode, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We introduce a new sublinear space data structure - the count-min sketch - for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point, range, and inner product queries to be approximately answered very quickly; in addition, it can be applied to solve several important problems in data streams such as finding quantiles, frequent items, etc. The time and space bounds we show for using the CM sketch to solve these problems significantly improve those previously known - typically from 1/ε2 to 1/ε in factor.

    Original languageEnglish (US)
    Pages (from-to)58-75
    Number of pages18
    JournalJournal of Algorithms
    Volume55
    Issue number1
    DOIs
    StatePublished - Apr 2005

    ASJC Scopus subject areas

    • Control and Optimization
    • Computational Mathematics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'An improved data stream summary: The count-min sketch and its applications'. Together they form a unique fingerprint.

    Cite this