Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bloom filters are good for search that does not scale

notpeerreviewed.com

Post reply on HN
Print view View original

31–40 of 43 posts

Re: Bloom filters are good for search that does not scale

#31

Post by 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

Re: Bloom filters are good for search that does not scale

#32

Post by lll-o-lll »

MattPalmer1086 wrote: post #3

May be true for offline full text search, but not true for online string search. I invented a very fast string search algorithm based on bloom filters. Our paper [1] was accepted to the Symposium of Experimental Algorithms 2024 [2]. Code can be found here [3]. [1] https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.S... [2] https://sea2024.univie.ac.at/accepted-papers/ [3] https://github.com/nishihatapalmer/Ha…

Looks really interesting! If I wanted to try one of these, which of the family would you recommend to start with?

Re: Bloom filters are good for search that does not scale

#33

Post by adamzwasserman »

hinkley wrote: post #30
adamzwasserman wrote: post #13

The "no sharing between filters" insight clicked for me on a different problem. I needed to filter items by tags. Bloom filter per item seemed clever - quick membership checks. But with thousands of items sharing dozens of tags, each filter re-encodes the same vocabulary. Pure waste. Switched to an inverted index (tag → item list) with bloom filters per chunk of the index. Now the tag vocabulary is shared, and bloom…

Why do these “inverted indexes” just look like indexes to me? Too much time with databases perhaps?

A non-unique index, yes.

Re: Bloom filters are good for search that does not scale

#35

Post by MattPalmer1086 »

lll-o-lll wrote: post #32
MattPalmer1086 wrote: post #3

May be true for offline full text search, but not true for online string search. I invented a very fast string search algorithm based on bloom filters. Our paper [1] was accepted to the Symposium of Experimental Algorithms 2024 [2]. Code can be found here [3]. [1] https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.S... [2] https://sea2024.univie.ac.at/accepted-papers/ [3] https://github.com/nishihatapalmer/Ha…

Looks really interesting! If I wanted to try one of these, which of the family would you recommend to start with?

Hashchain is the easiest to implement, but like many search algorithms can suffer from quadratic performance on really bad data and patterns (e.g. seaching for a long sequence of zero bytes in a text of zero bytes). In practice this is very rare.

If you want guaranteed linear performance in the worst case too, then LinearHashchain is the one to use. It is slightly more complex to implement as it builds in a KMP style verifier to make it linear (so almost two search algorithms are needed). It is actually about as fast as HashChain generally in the average case, so you don't lose out.

The others are either experimental or quite niche and not suitable for most purposes. SentinelHashchain is actually the fastest, but relies on being able to add a copy of the pattern at the end of the search text. Mostly this won't be possible in most search contexts, unless you control all memory allocations.

So I'd start with HashChain, and maybe play with the linear version later - most of it is the same, it just needs a bit more adding.

Re: Bloom filters are good for search that does not scale

#36

Post by farsa »

hinkley wrote: post #30
adamzwasserman wrote: post #13

The "no sharing between filters" insight clicked for me on a different problem. I needed to filter items by tags. Bloom filter per item seemed clever - quick membership checks. But with thousands of items sharing dozens of tags, each filter re-encodes the same vocabulary. Pure waste. Switched to an inverted index (tag → item list) with bloom filters per chunk of the index. Now the tag vocabulary is shared, and bloom…

Why do these “inverted indexes” just look like indexes to me? Too much time with databases perhaps?

The distinction is more clear when indexing actual text and applying tokenization. A "typical" index on a database column goes like "column(value => rows)". When people mention inverted indexes its usually in the context of full text search, where "column value" usually goes through tokenization and you build an index for all N tokens of a column "column:(token 1 => rows)", "column:(token 2 => rows)",... "column:(token N => rows)".

Re: Bloom filters are good for search that does not scale

#37

Post by NooneAtAll3 »

susam wrote: post #5

When I worked at RSA over a decade ago, we developed Bloom filter-based indexing to speed up querying on a proprietary database that was specialised for storing petabytes of network events and packet data. I implemented the core Bloom filter-based indexer based on MurmurHash2 functions and I was quite proud of the work I did back then. The resulting improvement in query performance looked impressive to our customers.…

what's RSA?

Re: Bloom filters are good for search that does not scale

#38

Post by twotwotwo »

susam wrote: post #5

When I worked at RSA over a decade ago, we developed Bloom filter-based indexing to speed up querying on a proprietary database that was specialised for storing petabytes of network events and packet data. I implemented the core Bloom filter-based indexer based on MurmurHash2 functions and I was quite proud of the work I did back then. The resulting improvement in query performance looked impressive to our customers.…

There is a largish category of tools now where, unlike in OLTP systems, a big focus is scanning data but quickly (O(n) but with a good constant): Redshift, Trino/Athena, ClickHouse, DuckDB among others.

Bloom filter indexing seems like a great fit if you ever need to do substring searches in a context like that, and for log searching in general. I haven't dug into what all packages have it, but it looks like at least ClickHouse does: https://clickhouse.com/docs/optimize/skipping-indexes#bloom-...

Re: Bloom filters are good for search that does not scale

#39

Post by FreakLegion »

hinkley wrote: post #25
philipkglass wrote: post #19

Earlier quoted context omitted.

There are a lot of "better than Bloom" filters that work similarly in some aspects. I have used Cuckoo [1] and Ribbon [2] filters for Bloom-type applications. If you have an application where you do a lot of one kind of searching, it may also be worth implementing a specialized variant of a data structure. I needed a Cuckoo-type filter on the JVM but only for 64 bit integers and I was able to make a smaller, faster c…

I wonder how often in the wild people are tuning for a 1% false positive rate versus a much lower one, like .1%. You do quickly reach data set sizes where even 1% introduces some strain on resources or responsiveness. Cuckoo claims 70% of the size of bloom for the same error rate, and the space is logarithmic to the error rate. Looks like about 6.6 bits per record versus 9.56 bits for bloom at 1%. But at .5% error ra…

Cuckoo filters can do even better with the small adjustment of using windows instead of buckets. See "3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit": https://scispace.com/pdf/3-5-way-cuckoo-hashing-for-the-pric.... (This significantly improves load factors rather than changing anything else about the filter, and ends up smaller than the semi-sorted variant for typical configurations, without the rigmarole.)

My fairly niche use case for these kinds of data structures was hardware firewalls running mostly on SRAM, which needed a sub one-in-a-billion false positive rate.

Re: Bloom filters are good for search that does not scale

#40

Post by kristianp »

NooneAtAll3 wrote: post #37
susam wrote: post #5

When I worked at RSA over a decade ago, we developed Bloom filter-based indexing to speed up querying on a proprietary database that was specialised for storing petabytes of network events and packet data. I implemented the core Bloom filter-based indexer based on MurmurHash2 functions and I was quite proud of the work I did back then. The resulting improvement in query performance looked impressive to our customers.…

what's RSA?

I assume it's RSA Security https://en.wikipedia.org/wiki/RSA_Security
Post reply on HN