Skip to content

Feedback: Bloom filter #959

@yeoleobun

Description

@yeoleobun

Page https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter
The formula of bits_per_item is incorrect

bits_per_item = -log(error)/ln(2)

According wikipedia Optimal_number_of_hash_functions, bits per item is: $-\frac{\ln(\epsilon)}{{\ln(2)}^2}$ ($\epsilon$ is error rate).

And the formula in the doc $-\frac{\ln(\epsilon)}{\ln(2)}$ is actually the optimal number of hash functions.

I calculate with python -log(error_rate) / (log(2) ** 2) get 9.58, 14.37, 19.17 for error rate 1 %, 0.1 %, 0.01% respectly.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions