Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Interactive Demo of Bloom Filters

jasondavies.com

Post reply on HN
Print view View original

31–40 of 56 posts

Re: Interactive Demo of Bloom Filters

#31

Post by biggerfisch »

taco_emoji wrote: post #29
Assossa wrote: post #18

If you want a simple explanation of bloom filters: To add to filter: 1) Get multiple hashes of the data. You can use the same hash function and increment the data each hash, or use multiple hash functions. You can do any amount of hashes from 1 to infinity, each filter size and dataset size has a sweet spot. 2) Mod (remainder) each hash by the filter size. The filter size can be any size, 1 to the maximum hash from y…

> a filter larger than your dataset is obviously useless This isn't obvious to me, can you explain?

At that point, it's harder to search/test than just looking at your dataset, so there's no point to making the size that large

Re: Interactive Demo of Bloom Filters

#34

Post by greenpizza13 »

SatvikBeri wrote: post #33
in9 wrote: post #32

What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?

Wouldn't a database lookup (with an index) be fast enough in that case? IIRC that's what Reddit does.

Presumably you have indexed based on username or the hash of a username, so the lookup is very inexpensive.

Re: Interactive Demo of Bloom Filters

#36

Post by striking »

in9 wrote: post #32

What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?

Bloom filters are O(1), but are probabilistic. So they're faster than even an indexed lookup in a database... but they don't always give you the correct answer.

Re: Interactive Demo of Bloom Filters

#37

Post by spike021 »

netcraft wrote: post #4

obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing

Cuckoo hashing was one of the more interesting concepts I learned back in school. Definitely a fun way of implementing a hash table.

Re: Interactive Demo of Bloom Filters

#38

Post by middleorigin »

avaer wrote: post #26
middleorigin wrote: post #21

Earlier quoted context omitted.

I have no idea why you think the name helps remove the need for a visualization. Besides I think "filter" is more apt than "table"—it doesn't store anything per se.

I never needed a picture to understand a hash table once I knew what a hash function was. If it were called a McCready table, that's one more trip to Wikipedia, plus one more every time I forget. Re: naming: It's a table of hash function results. It probabilistically stores a set. I don't see any filter here, though one use of the technique is indeed in filtering a list, though there are plenty more.

Right, but you're describing the implementation, which doesn't imply anything about its use. I prefer to name by the latter: the implemenation is just a detail on how the filter does its filtering.

Re: Interactive Demo of Bloom Filters

#39

Post by irl_zebra »

biggerfisch wrote: post #31
taco_emoji wrote: post #29

Earlier quoted context omitted.

> a filter larger than your dataset is obviously useless This isn't obvious to me, can you explain?

At that point, it's harder to search/test than just looking at your dataset, so there's no point to making the size that large

Well,the bloom filter only uses a tiny bit of space per data element and doesn't actually store the data. When searching the data itself, you're often searching through the actual data, which is more intensive and slow.
Post reply on HN