Approximating Data with the Count-Min Sketch

Abstract

Faced with handling multiple large data sets in modern data-processing settings, researchers have proposed sketch data structures that capture salient properties while occupying little memory and that update or probe quickly. In particular, the Count-Min sketch has proven effective for a variety of applications. It concurrently tracks many item counts with surprisingly strong accuracy.