What & Some notations

It allows you to test if an element most likely belongs to a set, or if it absolutely doesn’t.

A Probability method with FP possible, FN never.

Pre-content: True/False Positive/Negative

For a event E, there is a method T try to assert E whether happen or not(T{\oplus} or F{\circleddash}), and we got the final result R(T or F).
The type true or false stand for a state that a result is corresponding the test or not. P/N is meaning the test T's result.

type result
TP Test {\oplus}; Result {\oplus}
TN Test {\circleddash}; Result {\circleddash}
FP Test {\oplus}; Result {\circleddash}
FN Test {\circleddash}; Result {\oplus}

The worst type is FN because the result just happened as test refer no.

workaround

contents

  1. an array arr with structure {0,1}n{\{0,1\}^n}, n is the size;
  2. hash function H(element){H(element)} to get arr's indices.

workflow

pseudo code:

for i in indices:
  if arr[i] == 0:
    return false; // element not the part of arr
return true;  //  most likely the part of arr

Pros and Cons

Pros:

  1. space efficient;
  2. fast;
  3. No False Negative

Cons:

  1. can't remove element {\to} downgrade by the age;

Distribute(multi-files) the bloom filter files can reduce the effect of cons.1.

Refer