4 ms·
What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?
by in9 9y ago
What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?
- joeblau 9y agoThey are also helpful in terms of space savings. I worked at a startup in Palo Alto in 2011 where we used a 100 GB in memory (Redis) Bloom Filter to de-duplcate links coming in from a real-time social media stream (Facebook, Twitter, Forums, etc..). While Bloom Filter does introduce false positives (collisions) we were willing to take the bet on that rather than allowing duplicate social media posts in our pipeline. If we wanted to store this information in a regular hash table, we would require a lot more space than the 1 bit per entry of a Bloom Filter.
- SatvikBeri 9y agoWouldn't a database lookup (with an index) be fast enough in that case? IIRC that's what Reddit does.
- in9 9y agoI have read about what reddit does, but idk if it was a simple (or hashed) database lookup or maybe a BF.
- greenpizza13 9y agoPresumably you have indexed based on username or the hash of a username, so the lookup is very inexpensive.
- taeric 9y agoYou could also send the bloom filter down to the client to filter out client side with high probability.
- deleted 9y ago[deleted]
- striking 9y agoBloom 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.