Count-Min Sketch (2019) | Hacker News Reader

Count-Min Sketch (2019)

florian.github.io

44 pointscolinb11 comments

Count min sketches are really neat. A colleague at my old company used them to implement DDoS mitigations in eBPF and wrote it up: https://blog.cloudflare.com/building-rakelimit/

The code is also open source, and I've improved on it a bit: https://github.com/lmb/socklimit Not production ready but a cool idea and implementation.

I was wondering anyone could shed some light on the "These hash functions should be pairwise independent" part. I don't know what pairwise independent means. My background is mostly in web so I am familiar with things like `sha256`, `sha1`, `md5` things like that. Would you use these kind of functions for Count-min Sketch?

I saw in your socklimit project looks like `fasthash64` and `hashlittle` I'm not familiar with those any insight or recommended reading to understand these hash functions?

p.s. googling pairwise independent hash functions did get me some college class reading but doesn't mention any named hash functions developed out in the world.

You probably don't need the hash to be cryptographically secure. The simplest solution might be to use several uniquely keyed siphash instances, as siphash is quite cheap to compute, was designed for use in hash tables, and two siphashes with different keys behave pairwise independent, which roughly means there are no observable correlations between them.

[1] https://en.wikipedia.org/wiki/SipHash

I think we tried siphash at some point, unfortunately it's significantly slower than the two hash functions we ended up using.

Those hash functions are (or were) cryptographically secure. They aim to prevent many different kinds of attacks that may be launched on hashed data. There are many other noncryptographic ways to use hashes (like writing your own dictionary) that do not need the protections cryptographic hashes give you and therefore can trade those protections for performance.

Pairwise independence basically means that applying 2 different hash functions to the same key produces 2 distinct/seemingly random values. There's a much more precise mathematical definition but that's the essence.

We ended up with fasthash64 and lookup3 by looking for a fast hash that is easy to port to the restricted subset of C supported by eBPF with minimal changes. https://github.com/rurban/smhasher is a great resource for that.

I would probably choose different, more robust hash functions if I was targeting regular C.

This reminds me of the HyperLoglog [1] algorithm for approximating the cardinality of a huge set with limited memory.

[1] https://en.wikipedia.org/wiki/HyperLogLog

I remember learning about it from Redis: https://redis.io/docs/data-types/hyperloglogs/

Yes, they both fall under the broad category of randomized algorithms, and under "magic you can perform with hash functions" in my personal taxonomy.

> "magic you can perform with hash functions"

I really would love to see a book that basically just covers all the cool data structures people have come up with using hash functions.

I wonder if this would be a good data stucture to use to approximately find the most common substrings for inputs where doing so exhaustively would lead to too large memory overhead. For example to "train" a dictionary for compression. I was thinking something like:

    1. pick a substring length L to look for
    2. pick a number M for how many "most common substrings
       of length L" we wish to find
    3. initiate a count-min sketch for approximate counting
       of substrings, and an array of size M for keeping
       track of the top M substrings
    4. do a linear scan over the input (length N) to count
       each substring of length L (so ideally we'd be using
       rolling hashes for the count-min sketch)

We probably would have some false positives, and partialy overlapping substrings (I expect the latter is a difficult problem to solve elegantly, unless scanning over the text in steps of L works better than I think it would), but it might be an efficient heuristic.

The exhaustive search would be almost the same but use a prefix tree (aka trie) instead of a CMS, which has good average case overhead because tree, but if we're dealing with a "every substring is as unique as possible" worst case scenarios memory overhead could blow up to [input size times fairly big constant].

Said worst case scenario is quite easy to construct btw, just start with https://oeis.org/A142150 using 8 bit numbers, then modify to exhaust all remaining three-number combinations after exhausting all unique pair combinations, and so on.

Reply on news.ycombinator.com