# Searching with Bloom Filters

BOLT Talks · March 18, 2021

## The problem

Letting readers search my static sites.

## The solution

## That works, but...

Visitors had to download an __8 MB__ index file.

Could I have a search index for less?

## Bloom filters

“Is <this thing> in <that group>?”

You’ve likely used them already...

“Is __this site__ in __the naughty list__?”

“Is __this word__ in __that document__?”

- “Definitely not.”
- “Possibly yes.”

### Building blocks

- An array of
*n* bits.
*m* independent hash functions.

### Hash function

*data (any size)* → *value (fixed size)*

Where am I supposed to find

*m* independent hash
functions?

*
g*_{i}(x) = h_{1}(x) + ih_{2}(x) + i^{2}
mod n

## Absurdly simple example

(10 bits, 1 hash function)

## Reducing the error rate

(100 bits, 4 hash functions)

## Counting Bloom filters

Relevant search results by term frequency.

## Searching the site

One Bloom filter per document.