[HN Gopher] Bloom filters explained in a single image
___________________________________________________________________
Bloom filters explained in a single image
Author : polyrand
Score : 73 points
Date : 2021-04-11 17:36 UTC (5 hours ago)
(HTM) web link (exampl.io)
(TXT) w3m dump (exampl.io)
| reivalc wrote:
| thanks 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 wrote:
| This 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-
| filter...
| tyingq wrote:
| For 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-f...
| bradleyjg wrote:
| What 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 wrote:
| That was what was going through my mind too! What makes it so
| fascinating compared to other beautiful structures?
| Marazan wrote:
| They are easy to explain.
| joshlemer wrote:
| What other beautiful structures come to mind for you?
| polyrand wrote:
| Hi, 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 wrote:
| Hi 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.
| victor106 wrote:
| https://github.com/codahale/shamir
|
| A beautiful Beautiful algorithm
| polyrand wrote:
| Thanks for the suggestion! I had never heard about it, but
| like you said, it looks like an elegant, "simple" and
| useful algorithm. I'll definitely look into it!
| boyter wrote:
| Because despite all the posts a lot of people still don't get
| how they work.
|
| I did a brown bag where I work recently when I walked though
| how to implement one and was approached after by some of the
| smartest engineers I know saying thank you I think I finally
| get it.
| throw14082020 wrote:
| If they were called Leaky HashSets/ leaky dictionaries i don't
| think it would be as popular. Monads and bloom filters both
| have names that don't help the meaning.
| einpoklum wrote:
| Maybe the fact that they seem to be massively under-utilized,
| compared to hash tables? Despite being not much more
| complicated than hash tables?
|
| Also, you don't seem to have them available in popular
| container or general-purpose libraries.
| bryzaguy wrote:
| Can 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 wrote:
| Yes that's exactly right. Taking the length of a string could
| be considered a hash function, it's just a very poor one.
| [deleted]
| superasn wrote:
| I 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
| throw14082020 wrote:
| Yes thanks, also 2.5x is not supported by youtube, so i use
| https://chrome.google.com/webstore/detail/youtube-playback-s...
| throw14082020 wrote:
| > Bloom filters test if an element is part of a set, without
| needing to store the entire set
|
| https://python.land/bloom-filter
|
| There.
| anon_tor_12345 wrote:
| "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/S138912861...
|
| is a much better "single image" explanation (insofar as any
| single image could be sufficiently explanatory) of bloom filters.
| tofof wrote:
| Fulltext and figures of that paywalled journal article
| available here:
|
| http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.428...
| anon_tor_12345 wrote:
| ah thanks i didn't realize i had my institutional account
| logged in
| eis wrote:
| Bloom 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 wrote:
| This was easier to digest than the "image". Thanks.
| polyrand wrote:
| Thanks 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!
| notacoward wrote:
| Fun 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.
| tonke90 wrote:
| I'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?
| mimimi31 wrote:
| You 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/cacheeffic...
| avidiax wrote:
| 1) 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.
| polyrand wrote:
| Hi, 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/ [1] https://excalidraw.com/ [2]
| https://drwn.io/
| jdhendrickson wrote:
| Evans 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 wrote:
| To 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
| joshlemer wrote:
| I'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".
| vangelis wrote:
| My first thought about Bloom filters is always what does this
| have to do with shaders.
| FatalLogic wrote:
| Can this be explained, more simply, by saying that many different
| strings will be represented by a single hash?
| foreigner wrote:
| I think of them as Hashtables minus collision handling.
| cjohansson wrote:
| I 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
| kowlo wrote:
| This 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!
___________________________________________________________________
(page generated 2021-04-11 23:02 UTC)