2
$\begingroup$

I don't understand the use case of count min sketch. Based on Count–min sketch, it says "serves as a frequency table of events in a stream of data.".

If I know there are N types of events, why can't I just allocate an array of N slots or a hashmap to keep track of the event frequencies as the stream is ingested?

Am I right to say the use case is when N is unknown or N is so large that it is not possible to keep the entire frequency array/hashmap in memory?

|cite|improve this question
$\endgroup$
3
$\begingroup$

Sketches are data structures used in streaming algorithms. The idea is that while the stream is very long, the hardware processing it has limited memory. We want to be able to retain statistical information about the data without storing it completely.

You can find more information about sketching here.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

Yes, the use case is $N$ so large that the entire table would not fit in the main memory. For example, imagine that every event is tied to an IPv6 address. IPv6 uses 128 bits for each address, so you would in principle need an array with $2^{128}$ elements.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Even IPv4 is too big in many cases. In addition, its worth it to note that in some cases we may be sampling from an infinitely large set (for example all finite length strings) $\endgroup$ – DreamConspiracy Dec 29 '18 at 21:30
  • $\begingroup$ but i can still use a distributed hashmap right? Or is that not practical? $\endgroup$ – Mave Dec 30 '18 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.