Search code examples
javascriptcount-min-sketch

Use which hash functions for count-min sketch?

I am trying to implement count-min sketch with JavaScript. As I need some hash functions, I can not figure out which ones I can/should/must use. Any suggestions?

If this question is stupid, I'd appreciate a hint. Thanks

Solution

  • I think the solution is universal hashing, where you chose random hashfunctions out of a family of hashfunctions. When

    • m = universe, e.g. 32 bit which is 2^32-1 possibilities
    • p = next prime above m, e.g. 4294967311
    • a,b = randomly chosen with 0 < a < p and 0 <= b < p

    Then

    • h_a,b(x)=((ax+b)mod p)mod m)

    is universal.

    There is plenty of information online, starting with Wikipedia (https://en.wikipedia.org/wiki/Universal_hashing).