A global optimum is the best value of a function over its relevant domain. In Bloom filter design, it identifies the hash-function count k that minimizes the false-positive ratio while n, the element count, and m, the available bits, remain fixed. section 4.10.1
The optimization proceeds by:
- Expressing the false-positive ratio as a function f(k). section 4.10.1
- Applying natural logarithms so the exponent can be minimized instead. section 4.10.1
- Setting the first derivative to zero, then checking that the stationary point is a minimum. section 4.10.1
Choosing the number of hash functions
The calculation produces k = ln(2)·m/n. Because k must be an integer, round the result; larger k values increase insertion and lookup work because more hash functions must be computed. section 4.10.1
