6 ms·
Bloom filters explained in a single image
- anon_tor_12345 6y ago"bloom filters explain in a single image" where 90% of the image is text. so just bloom filters explained in 2-3 paragraphs? fig 3 here https://www.sciencedirect.com/science/article/pii/S1389128613003083#f0015 https://www.sciencedirect.com/science/article/pii/S138912861... is a much better "single image" explanation (insofar as any single image could be sufficiently explanatory) of bloom filters.
- tofof 6y agoFulltext and figures of that paywalled journal article available here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.428.7196&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.428...
- anon_tor_12345 6y agoah thanks i didn't realize i had my institutional account logged in
- notacoward 6y agoFun fact: the original pre-computer punch cards used for the census etc. were quite like Bloom filters with degenerate hash functions. Some of the same principles of key number/width, density, and pollution even apply. I've often thought that would be a good place to start, if I ever had to explain Bloom filters to a layman or beginner.
- vangelis 6y agoMy first thought about Bloom filters is always what does this have to do with shaders.
- FatalLogic 6y agoCan this be explained, more simply, by saying that many different strings will be represented by a single hash?
- cjohansson 6y agoI don't think so because that is a property of hash-maps, rather it seems to test some properties of an item to know that it is not in the set or that it might be in the set
- foreigner 6y agoI think of them as Hashtables minus collision handling.
- kowlo 6y agoThis is great but the title is a little misleading for me. Perhaps "bloom filters explained in a poster"... This contains multiple paragraphs and figures. You couldn't screenshot a wikipedia page and claim the same!
- tyingq 6y agoFor a really high level that includes how people practically use one with storage, I like this simple image: https://academy.bit2me.com/wp-content/uploads/2020/06/como-funciona-un-filtro-bloom-1024x576.webp https://academy.bit2me.com/wp-content/uploads/2020/06/como-f...
- bradleyjg 6y agoWhat is it about bloom filters that makes people want to explain them to others? I think I’ve seen more blog posts about them than any other cs topic, with the possible exception of monads.
- llaolleh 6y agoThat was what was going through my mind too! What makes it so fascinating compared to other beautiful structures?
- polyrand 6y agoHi, author here! I think you're absolutely right. In my case, I found them a beautiful data structure that is simple to understand but very useful. I also draw the images for learning myself about a topic, maybe others find the format useful, so I have started sharing them. But yes, I have definitely planned to draw/explain other data structures and computer science concepts. I did bloom filters now because I'm exploring concepts related to hashing and cryptography.
- bradleyjg 6y agoHi there! Not a criticism, I appreciate that you are putting out educational content. Rather, it was a genuine question. If you’re exploring cryptography, I highly recommend looking into Shamir’s secret sharing algorithm. It’s very elegant and doesn’t require much in the way of higher math to understand.
- polyrand 6y ago
- deleted 6y ago[deleted]
- superasn 6y agoI didn't understand a thing from this image but I was definitely intrigued and so I found a video on Youtube(1) that explains it quite simply (like for dummies) and now I fully understand it! You can watch it at 2.5x speed without missing out on anything: https://www.youtube.com/watch?v=kfFacplFY4Y https://www.youtube.com/watch?v=kfFacplFY4Y
- throw14082020 6y agoYes thanks, also 2.5x is not supported by youtube, so i use https://chrome.google.com/webstore/detail/youtube-playback-speed-co/hdannnflhlmdablckfkjpleikpphncik https://chrome.google.com/webstore/detail/youtube-playback-s...
- throw14082020 6y ago> Bloom filters test if an element is part of a set, without needing to store the entire set https://python.land/bloom-filter https://python.land/bloom-filter There.
- polyrand 6y agoHi, author here! I have created that site to summarize concepts I find interesting, while providing examples or use cases. My biggest inspiration comes from Julia Evans and her zines[0]. I started drawing the things I was learning about, and I thought the format could be useful for other people. Right now I'm diving into a mix of hashing functions/cryptography, data structures and databases. I usually spend a few days learning about a concept, and then I try to summarize it in a constrained drawing frame (I use Excalidraw[1] to do it and some logos from drwn.io[2]). I'm happy to accept suggestions about interesting topics to explore, draw and summarize. [0] https://wizardzines.com/ https://wizardzines.com/ [1] https://excalidraw.com/ https://excalidraw.com/ [2] https://drwn.io/ https://drwn.io/
- jdhendrickson 6y agoEvans is an absolute gem, and I'm delighted to see their influence on others. Thank you for trying to help others, it's always refreshing.
- gbrits 6y agoTo be complete something along the lines of: ‘if the answer is “maybe yes” a more computationally expensive is used to definitely decide yes or no’ should me added imo
- reivalc 6y agothanks for the post, it inspired this naive code: class BloomFilter: def __init__(self, size): self.f = [0] * size def contains(self, s): h1, h2, h3 = self.hashes(s) if self.f[h1] * self.f[h2] * self.f[h3] == 1: return 'Value might be in the set.' else: return 'Value is definitely not in the set.' def hashes(self, s): h1 = hash(s) % len(self.f) h2 = hash(s + 'salt') % len(self.f) h3 = hash(s + 'more salt') % len(self.f) return h1, h2, h3 def insert(self, s): h1, h2, h3 = self.hashes(s) self.f[h1] = self.f[h2] = self.f[h3] = 1 bf = BloomFilter(64) bf.insert('bill') print(f"{bf.contains('bill') = }") print(f"{bf.contains('bob') = }") Out: bf.contains('bill') = 'Value might be in the set.' bf.contains('bob') = 'Value is definitely not in the set.'
- polyrand 6y agoThis looks fantastic! I also implemented one from scratch[0], and I was doing something very similar at first. Then I found the Python hash() function returns different outputs for the same input when you restart the interpreter. I really like your implementation, it's functional and easy to understand! [0] https://ricardoanderegg.com/posts/understanding-bloom-filters/ https://ricardoanderegg.com/posts/understanding-bloom-filter...
- reivalc 6y agoNice! > found the Python hash() function returns different outputs for the same input when you restart the interpreter I wasn't aware of this >>
- eis 6y agoBloom filters explained in a single HN comment: They are an efficient implementation of a Set that contains hashes of the elements. bloomfilter.add("foo") will internally add hash("foo") to the Set bloomfilter.has("foo") checks if the Set contains hash("foo") False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true. No false negatives are possible. They are used when an actual check for an element in a datastructure is quite costly and the hitrate for not-in-the-datastructure is non-trivial and can therefor be skipped if the bloomfilter gives a negative.
- PUSH_AX 6y agoThis was easier to digest than the "image". Thanks.
- polyrand 6y agoThanks for your comment! (I'm the author of the image/poster). At first, I wanted to give a similar explanation than yours, but then decided to make it more verbose / less technical, and it ended up having more text that I would like to. Also, your last sentence is a great summary of when they should be used. I included a few use cases, but I should have also included something like what you said. I'll take that into account for future posts, thanks!
- kjeetgill 6y agoI think this is a great explanation for using a bloom filter and getting a feel for why you can get false positives but not false negatives. Super useful and succinct! This explanation could apply to a few hash-set style implimentations but I think it misses what made the bloom filter so beautiful and elegant when I'd discovered it. It's a specific data structure with it's own memory/performance/tuning profiles!
- Doxin 6y agoI don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure there are never any false negatives because bits only ever get turned on, never off. False positives are possible because of either direct hash collisions, or unrelated hashes turning on enough bits for a match.
- tonke90 6y agoI've used Bloom filters and found them to be memory latency bound, as queries can not be cached (big data structure, random access). Any recommendations on how to speed up queries?
- avidiax 6y ago1) Don't access randomly. That means either that the hash function you use is more like a reducing/mapping function (i.e. order preserving), or you iterate in the hashed order of your data. Obviously, this only works for scans and batch processes, not random user queries unless you can batch them. 2) Have a leakier bloom that fits in your L1/L2 cache size. You may have to have 2 layers of bloom filters, and this will be highly dependent on the relative expenses of the various operations.
- mimimi31 6y agoYou could use Blocked Bloom Filters[1]. It's essentially many small Bloom Filters that each fit into a cache-line. The first hash function decides, which of the smaller Bloom Filters an element will be saved in and can still cause a cache miss. All subsequent accesses to the small Bloom Filters are cached. The main drawback is that, because the elements won't be completely evenly distributed among the small Bloom Filters, you need some additional space to compensate and keep the false positive rate low. [1] https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheefficientbloomfilters-jea.pdf https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic...
- bryzaguy 6y agoCan someone help me understand the value of hashing? If you’re using modulus to bucket, why not just use the string length or something? Is it because the values will distribute across buckets more uniformly?
- joshlemer 6y agoYes that's exactly right. Taking the length of a string could be considered a hash function, it's just a very poor one.
- joshlemer 6y agoI've just thought about how you could also have a "Bloom Map", basically as a HashSet is to Bloom Filter, a HashMap would be to a Bloom Map. It would be able to answer lookups with either "Definitely not present" or "Might map to value XYZ".
- hinkley 6y agoA use of the bloom filter is to determine whether you need to make an expensive call to storage to check for a match. You use a smaller fraction of memory to avoid 99 out of 100 disk accesses than you would to have a full index of the data.
- sullyj3 6y agoWhat's the intuition behind the name?