8 ms·

I have wondered if bloom filters could be used as a cache on hash tables. It really comes down to if the bloom filter hashes can be computed significantly faste

I have wondered if bloom filters could be used as a cache on hash tables. It really comes down to if the bloom filter hashes can be computed significantly faster then doing the hashmap lookup (which includes hashing and probing).

aaronblohowiak 4y ago
that is a very common application of them, afaiu. though, the size and locality of the hashtable plays a significant role here. i may be taking a too generalized view of what you mean by "hash table"
vaibhavsagar 4y ago
Doing a hashmap lookup is already very much like using a bloom filter: for any addressing scheme, if an element exists at a particular location, then either the key exists or it's a false positive. If no element exists, then there's no way the key exists. Adding an extra bloom filter would then come down to trading off space usage against a different probability of false positives, in addition to an extra lookup, and I think one would have to contrive an extremely unlikely scenario for it to make sense.
- tialaramex 4y ago
  Sometimes "Does anything in this category exist?" is constantly needed and must be as fast as possible - especially if the answer is often "No", while "What is it exactly?" is more rarely needed and it's OK that it's slower. The Bloom filter gives you quick "No" answers for much less size than a hash table, in exchange for not being able to answer the second question at all. We built distributed database software, years ago when 40GB was a lot of data, and that used Bloom filters so that if you asked "Show me everything about vaibhavsagar, tialaramex, dang, and celeritascelery" it could do a Bloom filter check, identify that there isn't any data about celeritascelery and dang and immediately cut in half the work to be done, before going to the disk to pull in actual hash tables where records for tialaramex and vaibhavsagar would exist if the positive from the Bloom filter wasn't a false positive. The UX is nice too because it can make typos instant. For every municipality in Texas, show me the CesusCount. Instant zero records. Oh, right, not CesusCount I wanted CensusCount with an N.
bo1024 4y ago
1. Remember that a bloom filter only answers yes/no questions. So it can't cache hash table values, but it can cache set membership (is X in the hash table?). 2. Rather than speed per se, a better reason is space. You have a small bloom filter that lives close to the query. The query asks "is this entry in the hash table?" and get a local answer from the bloom filter, either "no" or "maybe yes". The answer is fast not because the hashing is fast, but because the small size allows it to be local and fast. Only for the "maybe yes" answers do you look it up in the hash table which is large and lives far away. This saves a lot of time if most answers are "no".
- dspillett 4y ago
  > Remember that a bloom filter only answers yes/no questions. Will, to nit-pick: the results from querying a bloom filter are either “no” or “maybe”, where the strength of the maybe varies from “are you feeling lucky?” to “almost definitely” depending on how well it is designed for the data it has been populated with.
  - smegsicle 4y ago
    the answer is no/maybe, but it's still a yes/no question as typically used
    - dspillett 4y ago
      I was about to make a very pedantic point, but thinking about it I'm actually wrong… If the question is phrased oddly then it does give yes/no answers: “Is <item> definitely not in <set>?”.
fxtentacle 4y ago
Yes. I forgot where, but I saw one game engine have bitmaps that where exactly 64 bytes as a super quick pre-check that fits into one CPU cache line => much faster than RAM access.

aaronblohowiak 4y ago

that is a very common application of them, afaiu. though, the size and locality of the hashtable plays a significant role here. i may be taking a too generalized view of what you mean by "hash table"

vaibhavsagar 4y ago

Doing a hashmap lookup is already very much like using a bloom filter: for any addressing scheme, if an element exists at a particular location, then either the key exists or it's a false positive. If no element exists, then there's no way the key exists. Adding an extra bloom filter would then come down to trading off space usage against a different probability of false positives, in addition to an extra lookup, and I think one would have to contrive an extremely unlikely scenario for it to make sense.

tialaramex 4y ago
Sometimes "Does anything in this category exist?" is constantly needed and must be as fast as possible - especially if the answer is often "No", while "What is it exactly?" is more rarely needed and it's OK that it's slower. The Bloom filter gives you quick "No" answers for much less size than a hash table, in exchange for not being able to answer the second question at all. We built distributed database software, years ago when 40GB was a lot of data, and that used Bloom filters so that if you asked "Show me everything about vaibhavsagar, tialaramex, dang, and celeritascelery" it could do a Bloom filter check, identify that there isn't any data about celeritascelery and dang and immediately cut in half the work to be done, before going to the disk to pull in actual hash tables where records for tialaramex and vaibhavsagar would exist if the positive from the Bloom filter wasn't a false positive. The UX is nice too because it can make typos instant. For every municipality in Texas, show me the CesusCount. Instant zero records. Oh, right, not CesusCount I wanted CensusCount with an N.

bo1024 4y ago

1. Remember that a bloom filter only answers yes/no questions. So it can't cache hash table values, but it can cache set membership (is X in the hash table?). 2. Rather than speed per se, a better reason is space. You have a small bloom filter that lives close to the query. The query asks "is this entry in the hash table?" and get a local answer from the bloom filter, either "no" or "maybe yes". The answer is fast not because the hashing is fast, but because the small size allows it to be local and fast. Only for the "maybe yes" answers do you look it up in the hash table which is large and lives far away. This saves a lot of time if most answers are "no".

dspillett 4y ago
> Remember that a bloom filter only answers yes/no questions. Will, to nit-pick: the results from querying a bloom filter are either “no” or “maybe”, where the strength of the maybe varies from “are you feeling lucky?” to “almost definitely” depending on how well it is designed for the data it has been populated with.
- smegsicle 4y ago
  the answer is no/maybe, but it's still a yes/no question as typically used
  - dspillett 4y ago
    I was about to make a very pedantic point, but thinking about it I'm actually wrong… If the question is phrased oddly then it does give yes/no answers: “Is <item> definitely not in <set>?”.

fxtentacle 4y ago

Yes. I forgot where, but I saw one game engine have bitmaps that where exactly 64 bytes as a super quick pre-check that fits into one CPU cache line => much faster than RAM access.