Re:Understanding Bloom filters by building one
by dspillett on Sunday May 29, 2022 @08:37AM
(#31548649)
> 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.
Re:Understanding Bloom filters by building one
by smegsicle on Sunday May 29, 2022 @01:39PM
(#31551019)
the answer is no/maybe, but it's still a yes/no question as typically used
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".