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

Word-Aligned Bloom Filters

lemire.me

Post reply on HN
Print view View original

41–50 of 82 posts

Re: Word-Aligned Bloom Filters

#41

Post by cma »

6510 wrote: post #36
lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

let me butcher the concept for you :) say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that…

Isn't this just similar to hash prefixes and not a true bloom filter?

Re: Word-Aligned Bloom Filters

#42

Post by marginalia_nu »

Gh0stRAT wrote: post #37
marginalia_nu wrote: post #29

Earlier quoted context omitted.

Couldn't you just send deltas if that is the case? Surely the hourly updates wouldn't be hundreds of megabytes? I just tested extracting 5 million URLs from my web crawler and it was like 150 Mb in plain text. That's ignoring how easy it is to create compression schemes for URLs that slash their memory footprint by something like 80%.

Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter. As with anything, there are tradeoffs and your requirements can change…

> As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.

We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard.

> As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently.

Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching.

Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.

Re: Word-Aligned Bloom Filters

#43

Post by ghostly_s »

a11r wrote: post #33
lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

The original paper by Burton H. Bloom is only 5 pages and very readable. https://dl.acm.org/doi/10.1145/362686.362692

https://sci-hub.st/https://doi.org/10.1145/362686.362692

Re: Word-Aligned Bloom Filters

#44

Post by phkahler »

I suspect a bloom filter should use a separate array of bits for each hash function. This came up in a previous discussion where stated probability of collisions was "wrong" but not if it were actually implemented with separate bit arrays.

Re: Word-Aligned Bloom Filters

#45

Post by phkahler »

blondin wrote: post #30
Rendello wrote: post #8

I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…

yep, great fan of his work here. thanks for sharing that podcast. that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine! our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern o…

I was recently disappointed and frustrated to learn that GCC will be enabling vectorization at -O2 soon. The realization that you have to specify both -O3 AND an architecture to get it to use AVX basically invalidated a bunch of benchmarking and testing I had done.

What's the point of building with x86-64-v3 if all your code is built at -O2 without vectorization enabled? Doh!

Re: Word-Aligned Bloom Filters

#46

Post by vvanders »

blondin wrote: post #30
Rendello wrote: post #8

I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…

yep, great fan of his work here. thanks for sharing that podcast. that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine! our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern o…

If you like this stuff data oriented design[1] is a nice framework that isn't arch specific(but can be extended to be if you need to make more gains that are arch aware). Back when I worked in the PS3/X360 days engines written for PS3 had better cache locality(SPUs forced hard limits vs hitting a cache miss) and ran faster on the X360 as result well when ported.

You can do do fun things like using radix sort with bucket sizes that line up well with L2/L3 caches(saw a multi order of magnitude speedup for that one) and data aware layouts that net 10-30x speedups for the same data. Many RMDBs use similar approaches from what I understand as well.

[1] https://en.m.wikipedia.org/wiki/Data-oriented_design

Re: Word-Aligned Bloom Filters

#47

Post by robertlagrant »

dr_kiszonka wrote: post #38
lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

I will take an imposter over a grandiose narcissist any day! (But then I am an imposter too.)

> If everyone is am imposter, no one is!

- Syndrome

Re: Word-Aligned Bloom Filters

#48

Post by csense »

colmmacc wrote: post #34

I'm really suspicious about whether this would really work out in most workloads. On modern architectures, it's the random memory reference that kills performance. Predictive pre-fetching in the pipeline has a impossible time figuring out what to get ready in the caches with random lookups; it's not like a linear sweep. This style of bloom-filter needs to be quite large, and it pulls only one cache-line in per key lo…

> I'm really suspicious about whether this would really work out in most workloads.

What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache?

> On modern architectures, it's the random memory reference that kills performance

Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update to 1 random access per query/update.

> Ultimately it depends on cache pressure and how over-subscribed the cache is

The unspoken assumption in the article is that the Bloom filter is much bigger than cache.

If your Bloom filter fits in cache, or you're writing for something with superfast RAM like a GPU or a Xeon Phi or something, block Bloom filters are wasteful for you.

But I'm pretty sure the common case is writing normal applications running on reasonable general-purpose CPU's with Bloom filter sizes in the hundreds of MB or more. [1] [2]

[1] If the Bloom filter's smaller than hundreds of MB, your data's probably small enough that you decide Bloom filters aren't worth the hassle and just use a HashMap or language equivalent.

[2] If you're using a Bloom filter to do some sort of network stuff, like figuring out the set difference of two peers' objects in some p2p protocol, you probably don't care too much about block Bloom filters, because in this application memory access time is probably going to be dominated by network latency.

Re: Word-Aligned Bloom Filters

#49

Post by jameshart »

Gh0stRAT wrote: post #22
marginalia_nu wrote: post #11

Earlier quoted context omitted.

I'm curious if you have a concrete example of a case where lookups aren't cheap and a bloom filter can solve the problem. In general, bloom filters are mainly useful for the sort of data where lookups are cheap, that is, testing for membership of a set, and that is typically one of the operations a database does really well. In most cases where you just want to save a network roundtrip, a LRU cache is often a lot eas…

Imagine you're making a web browser plugin that blocks ads, or malicious sites. Let's assume the blocklist is a hundred megs (easily fits in ram) and your millions of users need to get the latest data at least hourly in order to keep up with the latest URLs that you want to block. Rather than distributing the entire blocklist to your userbase, you can instead send a bloom filter + an allowlist of the small handful of…

Additionally, this method avoids you having to distribute a list of dubious sites to your users.

Re: Word-Aligned Bloom Filters

#50

Post by gpderetta »

marginalia_nu wrote: post #21
spenczar5 wrote: post #14

Earlier quoted context omitted.

I use them in astronomical data indexing when doing cross-match searches. That is, “could there be a star or other moving object in within 0.5 arcsec of this point in the sky?” Sky catalogs have many billions of objects but the density per solid angle of the sky is extremely variable, and moving objects also make lookups really complicated. Sky catalogs are big enough that they are not storable in memory, and may be…

Then we're indeed back in the territory of useful use cases, typically characterized by data that is far bigger than the system memory.

Bloom filter generally are much smaller than the data they represent. So if your set fits on disk, the bf might fit in ram; if your data fits in ram, your bf might fit in L3 and so on.

Edit: in particular you might want to use bloom filters fir early rejects, when most of the set ownership queries are expected to fail.

Post reply on HN