Bloom filter | Docs

redis.io · 7,357 words · saved by 1 readers

A Bloom filter is a probabilistic data structure in Redis Stack that enables you to check if an element is present in a set using a very small memory space of a fixed size. Instead of storing all of the elements in the set, Bloom Filters store only the elements' hashed representation, thus sacrificing some precision. The trade-off is that Bloom Filters are very space-efficient and fast. A Bloom filter can guarantee the absence of an element from a set, but it can only give an estimation about its presence. So when it responds that an element is not present in a set (a negative answer), you can be sure that indeed is the case. But one out of every N positive answers will be wrong. Even though it looks unusual at a first glance, this kind of uncertainty still has its place in computer science. There are many cases out there where a negative answer will prevent more costly operations, for example checking if a username has been taken, if a credit card has been reported as stolen, if a use

Bloom filter | Docs {"categories":["docs","develop","stack","oss","rs","rc","oss","kubernetes","clients"],"description":"Bloom filters are a probabilistic data structure that checks for presence of an item in a set","duplicateOf":"head:data-ai-metadata","location":"body","title":"Bloom filter","tableOfContents":{"sections":[]},"codeExamples":[{"codetabsId":"bf_tutorial-stepbloom","commands":[{"complexity":"O(1)","name":"BF.RESERVE"},{"complexity":"O(k)","name":"BF.ADD"},{"complexity":"O(k)","name":"BF.EXISTS"},{"complexity":"O(k * n)","name":"BF.MADD"},{"complexity":"O(k * n)","name":"BF.MEXIS

Bloom filter | Docs

related reading