4
$\begingroup$

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each other key. This contrasts with the sorts of analyses that I've seen done elsewhere. For example, both the count sketch and count-min sketch only require 2-independent hash functions, as does a hash table that resolves collisions via chaining. (However, linear probing hash tables require 5-independence).

Has there been any work done into analyzing Bloom filters under the assumption that the hash functions used are, say, only $k$-independent? Or are any lower bounds known on the degree of independence required for Bloom filters to provide reasonable guarantees about false positives?

Improve this question
$\endgroup$
3
  • $\begingroup$ A cursory Google search reveals several papers on Bloom filters and hashing with limited independence. $\endgroup$
    – Chandra Chekuri
    Apr 28, 2019 at 20:18
  • $\begingroup$ @ChandraChekuri Perhaps I'm missing something, but the first page of Google search results doesn't seem to have anything along these lines popping up. There are lots of hits talking about having several independent hash functions, but that's separate from the strengths of those hash functions. That said, if I'm searching for the wrong term or simply misread what I'm looking at, please let me know! $\endgroup$
    – templatetypedef
    Apr 28, 2019 at 20:42
  • 1
    $\begingroup$ See Propositions 3.9 and 3.10 in eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf $\endgroup$
    – Sasho Nikolov
    May 1, 2019 at 7:41

0

Reset to default

Your Answer

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