Example – Reading a Bloom Filter

Published by Mario Oettler on

Blockchain Introduction Technical – Beginner to Intermediate Lesson 11 – Bloomfilter Example – Reading a Bloom Filter

The recipient of a bloom filter now needs to “read” it. This is done by iterating through all available strings and checking if it matches with the entry in the bloom filter.

We take the bloom filter from the example above with bits 2, 3, 9, e, and f set.

Our recipient has four strings to test.

  • CAT
  • BIRD
  • ELEPHANT
  • MOUSE

Let’s start with CAT. It would occupy bits 0 and 1. But they are not in our filter. That’s why we can say it is definitely not in the filter.

The next string is BIRD. It would occupy the bits e and d. Only e is in our filter but not d. That’s why we know BIRD is definitely not in the filter.

Now, we check ELEPHANT. It would occupy the bits e and f. And both, e and f, are in the filter. But we know the sender did not include it. That’s why we can only say. ELEPHANT might be in the filter. It is possible, but we cannot be sure. The reason for this is that bloom filters allow false positive matches. We think it is a match, but in reality, it is not. That’s why we call bloom filters probabilistic data structures.

Our last string is HOUSE. It would occupy the 2 and 3. And again, both are in the filter. And again, the receiver (or reader) of the bloom filter doesn’t know what the sender (creator) really put into it. Hence, we can only say HOUSE might be in the filter.

The following table shows the bits each string would occupy.

StringBitBitIn Filter?
CAT01Definitely not in filter
BIRDedDefinitely not in filter
ELEPHANTefProbably in the filter
HOUSE23Probably in the filter

Previous Topic
Back to Lesson
Next Topic
Categories:
if()