<p>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).</p>

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

CC BY-SA 4.0
2019-04-28T20:18:52.620Z
A cursory Google search reveals several papers on Bloom filters and hashing with limited independence.
Chandra Chekuri
CC BY-SA 4.0
2019-04-28T20:42:05.787Z
@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!
templatetypedef
CC BY-SA 4.0
2019-05-01T07:41:23.140Z
See Propositions 3.9 and 3.10 in https://www.eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf
Sasho Nikolov
<ds.data-structures><hash-function><independence>
What degree of hash function independence is needed for Bloom filters?
templatetypedef
# What degree of hash function independence is needed for Bloom filters?

(Asked by: username_0 on 2019-04-26)

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?

**Tags:** ds.data-structures, hash-function, independence

> **Comments:**
> **username_1**: A cursory Google search reveals several papers on Bloom filters and hashing with limited independence.  
> **username_0**: @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!  
> **username_2**: See Propositions 3.9 and 3.10 in https://www.eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf  

---

## 0 answers

