[pncnmnp]

When my friends and I were undergrads (3rd year, I believe), we had an absolute blast exploring this exact topic - the intersection of Bloom Filters and client side searching. So much so that it became part of our undergrad thesis.

It all started when Stavros's blog was circulated on Hacker News! The way we approached the search part was by using "Spectral Bloom Filters" - https://theory.stanford.edu/~matias/papers/sbf-sigmod-03.pdf - which is based on a paper by Saar Cohen and Yossi Matias from the early 2000s - its basically an iteration on the counting bloom filters. We used the minimal selection and minimal increase algorithm from the paper for insertion and ranking of results.

I wrote a blog on it too - https://pncnmnp.github.io/blogs/spectral-bloom-filters.html

Some slides - https://pncnmnp.github.io/blogs/sthir-talk-2020.pdf