Fun fact: for a smaller search usecase, using Bloom filters to power a full-text search wins over inverted indexes. Here’s the counterintuitive insight…
An inverted index stores the entire dictionary and maps each word to document IDs. This means storing actual strings, tree structures for lookups, and pointers. For a small dataset with 50 documents, this overhead becomes significant.
Bloom filters sidestep all of this. They use about 10 bits per word and avoid storing strings entirely. With 1,000 distinct words per document, each filter is just 1.25KB. For 50 documents, that’s roughly 62KB total, small enough to ship to the browser with our page load.
Yes, we are doing O(n) lookups by checking every document’s filter. But when n is 50 or even 500, that’s perfectly acceptable. The speed of checking 50 compact bloom filters beats the complexity of maintaining string comparisons and tree traversal for such a small corpus.
The trade-off flips at scale. Once we have thousands of documents, inverted indexes become more efficient because they store the dictionary once and share it across all documents. The more documents we add, the better the space efficiency gets.
Bloom filters do not share information. Each one encodes its dictionary independently, so adding more documents just multiplies the storage and computation cost linearly.
Thus, for a smaller dataset, this counterintuitive approach is all three - space, time, and compute efficient.
Hope this helps.