Bloom Filter
A space-efficient probabilistic data structure that uses a bit array and multiple hash functions to test whether an element is a member of a set. It produces false positives but never false negatives, and is commonly used for cache penetration protection and membership queries.
Timeline (last 90 days)
A Bloom Filter uses a bit array and several hash functions; when inserting an element, multiple hash positions are set to 1, and during a query, it checks whether all corresponding bits are 1.
A Bloom Filter can only produce false positives (incorrectly judging that an element is present) and will never produce false negatives (failing to detect an element that is present).
The Cuckoo Filter is an improved variant of the Bloom Filter that supports deletion operations and achieves higher space efficiency at the same false positive rate.
A common engineering trade-off for distributed Bloom Filters is to periodically perform a bitwise OR merge of the bit arrays from each node, accepting a brief inconsistency window in exchange for low-latency local queries.
All Facts (4)
A Bloom Filter uses a bit array and several hash functions; when inserting an element, multiple hash positions are set to 1, and during a query, it checks whether all corresponding bits are 1.
50%UnverifiedA Bloom Filter can only produce false positives (incorrectly judging that an element is present) and will never produce false negatives (failing to detect an element that is present).
50%UnverifiedThe Cuckoo Filter is an improved variant of the Bloom Filter that supports deletion operations and achieves higher space efficiency at the same false positive rate.
50%UnverifiedA common engineering trade-off for distributed Bloom Filters is to periodically perform a bitwise OR merge of the bit arrays from each node, accepting a brief inconsistency window in exchange for low-latency local queries.
50%