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

What are Bloom filters? (2015)

medium.com

Post reply on HN
Print view View original

51–60 of 71 posts

Re: What are Bloom filters? (2015)

#51

Post by zardeh »

jedberg wrote: post #40
Retric wrote: post #24

Earlier quoted context omitted.

A list of votes per user per page would also work. ~90% of the time that list would be empty, if it's not your likely going to eventually need to know which specific items where voted on so might as well just load them all. Further, voting records are just not that big a data structure. Sure, it's much better than a poor implementation and might be a great optimization to bolt onto a different design, but again it's…

> A list of votes per user per page would also work. ~90% of the time that list would be empty, Not really. People tend to vote on one or two things on a page. So you'll have a long list of people who voted on one or two of the 1000+ items, and now you've had to do an extra lookup. It's a lot faster to just go straight for the votes and take advantage of the bloom filter.

You work(ed) at reddit, d(o|idi)n't you?

Re: What are Bloom filters? (2015)

#52

Post by msane »

gwbas1c wrote: post #41

I read about halfway into this article, and when the author started talking about Javascript, the "this" keyword, and the politics about the job, I stopped. What does that have to do with bloom filters? Get to the point!

I don't know, the first 5 paragraphs were about his lunch.

Re: What are Bloom filters? (2015)

#54

Post by supercoder »

gwbas1c wrote: post #41

I read about halfway into this article, and when the author started talking about Javascript, the "this" keyword, and the politics about the job, I stopped. What does that have to do with bloom filters? Get to the point!

Bloom filters are cool , but the writer is pretty annoying. It's written like they discovered bloom filters or something.

Just read the last section.

Re: What are Bloom filters? (2015)

#55

Post by supercoder »

taeric wrote: post #23

Bloom filters originally upset me because I expected the word "Bloom" to refer to an action of the algorithm. Not so someone's name. I'm fond of Concierge filtering as an easy description of how they work. I view them as a brief conversation with the front desk staff at a hotel to determine if someone is there. "Is anyone here wearing a hat? Is anyone here over 6'? Did anyone come in carrying a briefcase?"

Agreed!

Re: What are Bloom filters? (2015)

#56

Post by lpage »

bradleyjg wrote: post #13

Whenever considering a bloom filter also look at cuckoo filters. There are pros and cons of each approach. See https://bdupras.github.io/filter-tutorial/ and http://11011110.livejournal.com/327681.html as well as the corresponding HN discussions https://news.ycombinator.com/item?id=12124722 and https://news.ycombinator.com/item?id=11795779

For that matter, cuckoo hashing [1] in general is an interesting topic. Take a look at its application to cache oblivious dictionaries [2]. They work quite well in practice, especially for space constrained hash tables (e.g. caches).

[1] https://en.wikipedia.org/wiki/Cuckoo_hashing

[2] https://arxiv.org/abs/1107.4378

Re: What are Bloom filters? (2015)

#57

Post by Kenji »

Ah, another article about Bloom filters on HN.

That reminds me, does anyone know if Windows 10 uses bloom filters? Specifically, if I have a folder with a lot of files inside and I paste a file into it, if the file name is different from all the names of the files in the folder, it is nearly instant (true negative, no further testing needed) but if the file name matches one of the names, it takes significantly longer (true or false positive of bloom filter -> check all files manually for a match).

It's just something that's been going through my mind lately when I moved files.

Re: What are Bloom filters? (2015)

#58

Post by Retric »

jedberg wrote: post #40
Retric wrote: post #24

Earlier quoted context omitted.

A list of votes per user per page would also work. ~90% of the time that list would be empty, if it's not your likely going to eventually need to know which specific items where voted on so might as well just load them all. Further, voting records are just not that big a data structure. Sure, it's much better than a poor implementation and might be a great optimization to bolt onto a different design, but again it's…

> A list of votes per user per page would also work. ~90% of the time that list would be empty, Not really. People tend to vote on one or two things on a page. So you'll have a long list of people who voted on one or two of the 1000+ items, and now you've had to do an extra lookup. It's a lot faster to just go straight for the votes and take advantage of the bloom filter.

Real world data wins so if you have real data then great a write up would be cool.

However, it's 100% empty the first time someone opens a link. If someone up votes there is no need to refresh, so they need to up vote and then refresh the page which I assume is less common. With lot's of pages that never get refreshed and a long tail of pages people go back to. So, my assumption is you can easily keep a vote list in memory for popular pages and everything else is basically a non issue.

As to matching up votes with items, I kind of think that's for client side JavaScript in most cases.

Re: What are Bloom filters? (2015)

#59

Post by Retric »

zardeh wrote: post #50
Retric wrote: post #35

Earlier quoted context omitted.

> How? Page has a list of people who have voted, and that list points to a list of their votes. Each comment has a a number for vote counts, but not a list of scores. User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k. On user vote, server look…

But that requires like entirely rearchitecting the reddit backend to be less efficient. A page has comments a comment has comments a comment has votes a vote has a user That is to say that a vote is a many to many join from user-comment. To do what you want, you'd also have to give the page the concept of "people who have voted on a comment that belongs to be or one of my children" >User opens page, they get a list o…

In your approach comments have votes the server must check the bloom filter for each comment then do a fetch for each match in the case of 500 votes that's 500 fetches which are at least votes * (log comments votes) because you can't trust the filter.

My approach that's client side most of the time. Further it's O (n) to compare matches between two sorted lists so just sort them in O (n log n). Further log 500 is faster than most hashes.

And of course for the most common case of no votes it's a single lookup and done.

PS: As to changing the back end, yes if the initial implementation is bad then you might have a point. But, again fixing the problem also works and produces far less code to maintain.

Re: What are Bloom filters? (2015)

#60

Post by booleandilemma »

taeric wrote: post #23

Bloom filters originally upset me because I expected the word "Bloom" to refer to an action of the algorithm. Not so someone's name. I'm fond of Concierge filtering as an easy description of how they work. I view them as a brief conversation with the front desk staff at a hotel to determine if someone is there. "Is anyone here wearing a hat? Is anyone here over 6'? Did anyone come in carrying a briefcase?"

How do you feel about shellsort?

https://en.m.wikipedia.org/wiki/Shellsort

Post reply on HN