Skip to content
Get started

Tuning a Bloom filter

You store 10610^6 keys in a Bloom filter backed by 1.251.25 MB of memory (exactly 10710^7 bits). Each key is inserted by setting the bits at kk independent uniform hash positions; a query reports 'present' if all kk of its bits are set. Choosing the integer kk that minimises the false-positive rate, what is that rate, in percent? (Use the standard approximation that bits are set independently.)

Show hints (3)+
  1. Write the probability that one particular bit is still 0 after all insertions.
  2. A false positive needs all kk probed bits set; minimise (1−e−kn/m)k(1-e^{-kn/m})^k over kk.
  3. The optimum sits where about half the bits are set.

Answer

Reveal answer →

0.819 (± 0.01)

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions