What are Bloom filters? (2015) • Hacker News Board

Re: What are Bloom filters? (2015)

#31

Post by nitrogen » Fri, Aug 05, 2016, 6:25 PM UTC

Retric wrote: post #24

jedberg wrote: post #14

Earlier quoted context omitted.

The place where bloom filters really shine is doing lookups on data where most of the time the data isn't there. For example, when you load a page on reddit, it has to check for a vote on every single comment on the page to see if you voted on it. Chances are 99% of the time you didn't vote on an item. Using the built in bloom filter in Cassandra, it can very quickly tell if you voted on an item without having to hit…

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…

At Reddit's size, wouldn't that just shift the problem from looking up votes to looking up lists? Millions of users times millions of articles? Seems like a fast way to get an early "no" would still be useful.

Re: What are Bloom filters? (2015)

#32

Post by zardeh » Fri, Aug 05, 2016, 6:28 PM UTC

Retric wrote: post #24

jedberg wrote: post #14

Earlier quoted context omitted.

The place where bloom filters really shine is doing lookups on data where most of the time the data isn't there. For example, when you load a page on reddit, it has to check for a vote on every single comment on the page to see if you voted on it. Chances are 99% of the time you didn't vote on an item. Using the built in bloom filter in Cassandra, it can very quickly tell if you voted on an item without having to hit…

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, 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.

How? This means you're now duplicating data, instead of organizing as

page has comments have comments have ... have votes

you now have

page has comments have comments have ... have votes page has list of special comments where you don't know where they are or what their parental hierarchy is and still need to look up in the list anyway.

you're duplicating the "has been voted on" field.

Re: What are Bloom filters? (2015)

#33

Post by nitrogen » Fri, Aug 05, 2016, 6:29 PM UTC

looki wrote: post #28

prashnts wrote: post #11

Earlier quoted context omitted.

No, it isn't. The problem here would be that you'd be essentially invalidating arbitrary hashes from the table with each operation where they share the same "row" (or address in a bitmap) with other hashes. Suppose we have a table such that "foo", "bar", "baz" all have overlapping entry -- if we attempt to remove any of them, we'd remove the rest also. This being said, you might be interested in `Counting filter' ins…

Thanks. That's what I meant with deleting "equivalent entries", I was wondering if there are cases where that would still be a net gain. But it makes sense that there are more specialized versions for such things. PS I don't understand why my comment was downvoted, is there something wrong with asking such questions here?

I don't understand why my comment was downvoted, is there something wrong with asking such questions here?

Not AFAIK, but sometimes people downvote questions that are based on misunderstandings or false premises. Give it some time and you'll probably be voted back up to where you started.

Re: What are Bloom filters? (2015)

#34

Post by chrisseaton » Fri, Aug 05, 2016, 6:35 PM UTC

nitrogen wrote: post #30

hinkley wrote: post #9

Earlier quoted context omitted.

I do believe you specifically asked: Isn't this standard in algorithms and data structures courses? And the answer was 'no'. It's okay to be publicly wrong. You wanted to learn something and now you know. But acting like you didn't ask it because you're feeling self-conscious just makes the whole thing awkward for everybody.

I certainly didn't get the impression that the OP's follow-up comment was trying to cover up a public display of ignorance. Rather it seemed to me that the comment about lacking a centralized curriculum was needlessly snarky and did not interpret the OP's comment charitably.

My comment was genuinely trying to help explain that there isn't a single curriculum! I didn't post the telling off that followed his response!

Re: What are Bloom filters? (2015)

#35

Post by Retric » Fri, Aug 05, 2016, 6:44 PM UTC

zardeh wrote: post #32

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, 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. How? This means you're now duplicating data, instead of organizing as page has comments have comments have ... have votes you now have page has comments have comments have ... have votes page has…

> 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 looks at past votes on page and adds it if missing then updates comment score.

Ok, you need every vote from each user and caching comment scores is really likely a no brainier, but I guess you could recalculate it.

PS: Not all comments are going to be loaded, but again if your sending <200 bytes for the full list 99.9% of the time then doing something else has limited value.

Re: What are Bloom filters? (2015)

#36

Post by s_q_b » Fri, Aug 05, 2016, 6:49 PM UTC

chrisseaton wrote: post #34

nitrogen wrote: post #30

Earlier quoted context omitted.

I certainly didn't get the impression that the OP's follow-up comment was trying to cover up a public display of ignorance. Rather it seemed to me that the comment about lacking a centralized curriculum was needlessly snarky and did not interpret the OP's comment charitably.

My comment was genuinely trying to help explain that there isn't a single curriculum! I didn't post the telling off that followed his response!

Fully agreed. Your comment was a fair question for clarification of what I meant by "curriculum". I thought I answered it fairly by clarifying that I meant topics generally covered by most universities in their in algorithms and data structures courses.

I'm not sure of the reason for the snark in the follow up. It was a fairly straightforward question and answer.

Re: What are Bloom filters? (2015)

#37

Post by nitrogen » Fri, Aug 05, 2016, 7:00 PM UTC

chrisseaton wrote: post #34

nitrogen wrote: post #30

Earlier quoted context omitted.

I certainly didn't get the impression that the OP's follow-up comment was trying to cover up a public display of ignorance. Rather it seemed to me that the comment about lacking a centralized curriculum was needlessly snarky and did not interpret the OP's comment charitably.

My comment was genuinely trying to help explain that there isn't a single curriculum! I didn't post the telling off that followed his response!

You are quite right. I must have conflated the tone of one comment and the text of the other in my mind when I was replying.

Re: What are Bloom filters? (2015)

#38

Post by Retric » Fri, Aug 05, 2016, 7:03 PM UTC

nitrogen wrote: post #31

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…

At Reddit's size, wouldn't that just shift the problem from looking up votes to looking up lists? Millions of users times millions of articles? Seems like a fast way to get an early "no" would still be useful.

Your looking it up once per page vs. once per comment. So, yes it might be faster, but when something takes 1% of total time speeding it up has massive diminishing returns.

Re: What are Bloom filters? (2015)

#39

Post by dalke » Fri, Aug 05, 2016, 7:34 PM UTC

pklausler wrote: post #25

drchickensalad wrote: post #17

Earlier quoted context omitted.

Is this in programming pearls? Otherwise where?

I saw it in a column in Comm. of the ACM a long time ago, sorry.

McIlroy's "Development of a Spelling List" (1982) paper is doi:10.1109/TCOM.1982.1095395 available at https://web.archive.org/web/20120324185456/http://unix-spell... . I found it from https://code.google.com/archive/p/unix-spell/ , which also says:

> It is interesting to note that one of the world's best compressor (paq8l) can compress the 250kb word list down to 48.5kb, less than the space taken by the lossy compression methods proposed in the paper! For comparison, regular modern compression methods (such as gzip, lzma etc) only achieve twice that size (85-90kb).

Bentley's commentary is in "A Spelling Checker", CACM 28(5): 456-462 (1985), doi:10.1145/3532.315102 , behind the paywall at http://dl.acm.org/citation.cfm?id=315102&dl=ACM&coll=DL&CFID... and in the book "Programming Pearls", Second Edition, according to http://www.linuxjournal.com/article/3846 .

Re: What are Bloom filters? (2015)

#40

Post by jedberg » Fri, Aug 05, 2016, 7:54 PM UTC

Retric wrote: post #24

jedberg wrote: post #14

Earlier quoted context omitted.

The place where bloom filters really shine is doing lookups on data where most of the time the data isn't there. For example, when you load a page on reddit, it has to check for a vote on every single comment on the page to see if you voted on it. Chances are 99% of the time you didn't vote on an item. Using the built in bloom filter in Cassandra, it can very quickly tell if you voted on an item without having to hit…

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.