From membership to retrieval

  • A Bloom filter lets you look up one bit per element of the set (and that bit is always 1). 1:01:13
  • Bloomier filters generalize this: associate an arbitrary r-bit string with every element, using n·r bits total. That is the retrieval problem. 1:01:13 1:01:43

What retrieval does not solve

  • It is not the dictionary problem — the keys themselves are never stored. 1:01:43
  • You cannot enumerate the set: holding the keys would need n words, and the structure only uses n·r bits. 1:02:18
  • Give it an element and it answers; ask it what it contains and it cannot say. 1:02:08

The guarantee

  • Static version only: all items and all strings are known up front. 1:02:31 1:16:03
  • No errors for members: x ∈ S ⇒ the correct r-bit string is returned. 1:02:54
  • Garbage for non-members: x ∉ S ⇒ an arbitrary r-bit string with no guarantee, and the structure cannot even tell it is wrong. 1:02:54 1:03:12
  • Attribution: Chazelle, Kilian, Rubinfeld and Tal, 2004. 1:14:51 1:15:31

The construction is deferred until cuckoo hashing is introduced, since it is built on a cuckoo hash table. 1:03:22 1:14:51