A derivative measures how a function changes as its input changes. In Bloom-filter design, derivatives help find the global minimum of the false-positive-rate function by optimizing k, the number of hash functions. section 4.10.1
Use derivatives to optimize the Bloom-filter parameter k:
- Treat the number of elements n and available storage m as constants. section 4.10.1
- Rewrite the false-positive function with logarithms and exponentiation to obtain an easier function g. section 4.10.1
- Set the first derivative of g(k) to zero, producing k = ln(2)m/n. section 4.10.1
- Use a second-order derivative check, round k to an integer, and weigh accuracy against insertion and lookup performance. section 4.10.1
Choosing the number of hash functions
Given fixed storage and an expected number of elements, differentiate the transformed false-positive function, solve for the stationary value of k, then round it and possibly choose a slightly smaller value to reduce computation. section 4.10.1
