# Overview Count-min (CM) Sketch is... #flashcard An extension of a [[Bloom Filter]] that allows for establishing an upper bound for the number of times and item has appeared in a stream of data. <!--ID: 1750528252914--> # Key Considerations The space-accuracy trade-off of CM Sketch is based on two parameters: #flashcard - Width (`w`) - controls collision probability. More width = fewer collisions = better accuracy - Depth (`d`) - controls confidence in the estimate. More depth = higher confidence # Pros <!--ID: 1750528252916--> # Cons # Use Cases Count-min Sketch works great when... #flashcard there is a large volume of data and not enough storage to count every item. It works well for use cases that meet the following use cases: 1. You need to be querying for counts 2. We need to have *known* items - our sketch does not tell us which items are present after we hash them 3. You need to be space constrained (otherwise just use a hash table) 4. You need to be able to tolerate an approximation (i.e. an upper-bound) Some examples that meet these properties are: - [[Top K]] - [[Caching]], specifically for [[LFU - Caching]] eviction policy <!--ID: 1750528252919--> # Related Topics