TECH DIGITAL RESOURCE LIBRARY

Rutgers, The State University of New Jersey


Latest Content From Rutgers, The State University of New Jersey

Whitepaper: An Improved Data Stream Summary: The Count-Min Sketch and Its Applications

by Rutgers, The State University of New JerseyJan 01, 2008

This research paper from Rutgers, The State University of New Jersey introduces a new sub linear space data structure - the Count-Min Sketch for summarizing data streams. This 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 quantizes, frequent items, etc. The time and space bounds author shows for using the CM sketch to solve these problems significantly improve those previously known typically from 1/""2 to 1/"" in factor.