# Count Sketch Count Sketch is a [probabilistic data structure](https://stackoverflow.com/a/35050835/1090562) which allows you to answer the following question: > Reading a stream of elements `a1`, `a2`, `a3`, ..., `an` where there can be many repeated elements, you the answer to the following question at any time: _How many `ai` elements have you seen so far?_ You can clearly get an exact answer at any time just by maintaining the mapping from `ai` to the count of those elements you've seen so far. Recording new observations costs _O(1)_, as does checking the observed count for a given element. However, it costs _O(n)_ space to store this mapping, where _n_ is the number of distinct elements. How is Count Sketch is going to help you? As with all probabilistic data structures you sacrifice certainty for space. Count Sketch allows you to select two parameters: **accuracy of the results** $\epsilon$ and **probability of bad estimate** $\delta$. --- Date: 20210901 Links to: [Computer Science MOC](Computer%20Science%20MOC.md) [Algorithms and Data Structures](Algorithms%20and%20Data%20Structures.md) [Count-min Sketch](Count-min%20Sketch.md) Tags: References: * [Stackoverflow explanation](https://stackoverflow.com/questions/6811351/explaining-the-count-sketch-algorithm)