False Positive Rate

Published by Mario Oettler on

Last Updated on 3. May 2023 by Martin Schuster

So far, we learned that bloom filters have a false-positive rate. This rate depends on three parameters:

  1. size of the filter in bit (e.g. 8 bit, 32 bit, 256 bit, etc).
  2. number of hash functions
  3. number of elements included in the bloom filter

We can calculate the probability of a false-positive match with this formula:

Where

  • m: size of the filter in bit
  • k: number of hash functions
  • n: number of elements in the filter
  • p: probability of a false positive match

Numerical Example

Calculate the probability p for a false positive match for the following table:

mknp
1632 
1635 
25635 
256105 
2562005 

Solution

mknp
16320,03309652
16350,238544399
256350,000185372
2561053,14614E-08
25620050,01772303

The following charts show the development of false positives depending on m, k, and n if the other parameters are constant.

False-positive rate depending on k.
False-positive rate depending on m.
False-positive rate depending on n.

Categories:

https://blockchain-academy.hs-mittweida.de/wp-content/uploads/2021/04/logo_bcam_rgb_gross.png

Welcome

Blockchain Academy

Continue with credential

No account yet?

Powered by Hidy

Register with Hidy


Register
Sign in

We need the following credential to register:

please select:

To create a new account, we need the following data from you:

We would appreciate the following additional information from you for the creation of your account:

Welcome

Blockchain Academy

Continue with credential

Already have an account?

Powered by Hidy

Sign in with Hidy


Register
Sign in

We need the following credential to log in:

please select:
Do you need assistance?
Click here to open chat.

Privacy Notice: This chat sends your questions to an external AI server.
How can we help you?
  • Please note: All questions, chat history, and feedback are sent to an external AI server for processing. Do not share sensitive personal information.

    All responses are generated by AI. Independently verify and fact-check all information before use.
  • No Chat History yet, start talking...