Comment on How we store 400M phone numbers with fast lookupComments−d_e_solomon11yThanks for posting this article. Would this be a good use case for a bloom filter?−fleitz11yMaybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM.Basically you'd waste more time (and money) than it could possibly be worth.−mamp11yYou could get away with much less memory using Redis hashes with a few more lines of code: http://redis.io/topics/memory-optimization.−bpicolo11yI mean, a bloom filter isn't super difficult, but it's also probabilistic instead of deterministic.−fleitz11yExactly, so you'd need the array anyway...Also, typically bloom filters don't come out of the box with the language you're using, so it's just more potential for bugs.A lookup on a sorted array should take 8.6 comparisons anyway, I bet the hashing takes longer...−d_e_solomon11yThat's true, good call.
Comments
Thanks for posting this article. Would this be a good use case for a bloom filter?
Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM.
Basically you'd waste more time (and money) than it could possibly be worth.
You could get away with much less memory using Redis hashes with a few more lines of code: http://redis.io/topics/memory-optimization.
I mean, a bloom filter isn't super difficult, but it's also probabilistic instead of deterministic.
Exactly, so you'd need the array anyway...
Also, typically bloom filters don't come out of the box with the language you're using, so it's just more potential for bugs.
A lookup on a sorted array should take 8.6 comparisons anyway, I bet the hashing takes longer...
That's true, good call.