Bloom Search

npm API reference

Full-text search for static sites.

Bloom Search is a JavaScript search library that indexes each document as a few Bloom filters instead of one shared word list. 

npm install @pacote/bloom-search
The headline in a Bloom filter: 6 words in 160 bits.

The problem

With no server to ask, search runs in the visitor’s browser and the index ships with the site. A conventional inverted index lists every word and every document it appears in. On a large site that is a lot of bytes before anyone has typed anything.

Bloom Search is for sites where that cost is too high and a hosted search service is not an option. It gives up some accuracy to get a smaller index, and tells you exactly which kind.

How it works

A Bloom filter is a row of bits and a few hash functions. Adding a word sets a few bits. Asking about a word checks the same bits: if any is unset, the word was never added; if all are set, it probably was. Try one by hand, or with counters instead of bits, which is what lets a word be removed.

Bloom Search keeps a set of filters per document. Adding a document runs its text through five steps. Here is one short passage going through all of them.

Original

“There! there again! there she breaches! right ahead! The White Whale, the White Whale!”

Tokens

there there again there she breaches right ahead the white whale the white whale

Stopwords

there (stop word) there (stop word) again (stop word) there (stop word) she (stop word) breaches right (stop word) ahead (stop word) the (stop word) white whale the (stop word) white whale

Stopwords are words so common they match almost every document and say nothing about any of them. Dropping them keeps the filters small.

Stems

breaches → breachwhitewhalewhitewhale

Stemming cuts a word back to its root, so “breaches” and “breaching” both become “breach”. A Bloom filter only answers for whole words, so stemming is how a search finds other forms of the word. Bloom Search takes any stemmer you give it. See what one does to a word.

Filters

seen 2× white, whale

seen 1× breach

The resulting stems are then counted, weighted by field, and grouped by how often they occur. Each group becomes its own Bloom filter.

A search runs the query through the same steps, then asks every document’s filters about each stem. Which filter answered says roughly how often the word occurs, and that frequency is combined with how rare the word is across the candidates (using tf-idf) to order the results. Tokens are double hashed with xxHash64, so the filters need only two fast hash computations per word.

Because the index holds filters and not words, it cannot be read back as text, though it can still answer searches. Only the summary fields you choose are stored in the clear. See what that looks like.

What you get

  • A compact index. Size follows how many distinct words each document has and the error rate you choose.
  • No false negatives. If a document contains the word, it is returned.
  • Query operators. +word requires, -word excludes and "two words" matches a phrase.
  • Ranking. Results come back best first, with weights per field.
  • Hooks. Plug in your own stemmer, tokenizer, stopword rule and preprocessing.
  • Plain data. The index is an object you can write to JSON or MessagePack at build time and load in the browser.

Trade-offs

  • False positives. A document can match a word it does not contain. At the default errorRate of 0.0001 that is about one lookup in ten thousand, per filter. Lower it and the index grows.
  • Whole words only. No prefixes, suffixes, substrings or fuzzy matching. A stemmer recovers some of this (“searching” finds “searched”); the rest is out of reach.
  • Approximate ranking. Frequency is known only to its bucket, not exactly.
  • It does not scale forever. Each document repeats its own vocabulary, whereas an inverted index shares it. “Bloom filters are good for search that does not scale” puts the crossover near 7,200 documents. Measure with your own content before you commit.
  • Build and browser must agree. Same stemmer, same seed, same tokenizer. Change one and you rebuild the index. The index carries a schema version, and load() throws on a mismatch.

Alternatives

The comparison measures five libraries on the same corpus. These are the trade-offs behind the numbers.

Library Index Good for
Bloom Search A set of Bloom filters per document Small to medium sites that want ranking and a small payload.
Lunr Inverted index Ranking, field boosting and stemming, when the full index is affordable.
Elasticlunr Inverted index Inspired by Lunr’s approach, with field search and query-time boosting.
MiniSearch Inverted index Prefix and fuzzy matching, with ranking.
Fuse.js Bitap algorithm Fuzzy matching on small data sets.