3 ms·
Is a bloom filter worth it in this case? With the optimal "k" hash functions of 10 and a "p" error rate of 0.001% (false positives of approximately 1 in 1000),
by developer2 9y ago
Is a bloom filter worth it in this case? With the optimal "k" hash functions of 10 and a "p" error rate of 0.001% (false positives of approximately 1 in 1000), a bloom filter for the 306,259,512 items will take 538 MB. Increasing the error rate to 0.01% (1 in 100) is still 358 MB. That's a sizeable filter to maintain in memory (then again... RAM is cheap).
I'd probably just shove the passwords into a database, limiting the index prefix to the first X characters to reduce index size.
- captn3m0 9y agoDistributing a 538 MB file (which can be compressed further) is much easier.
- wongarsu 9y agoWhat are the actual use cases where this size difference matters? I distributing to a general audience, 0.5GB and 10GB isn't that much of a difference, and most people are more equipped for handling lists of strings than for handling bloom filters.
- bradleyjg 9y ago>which can be compressed further Can it? I think of a bloom filter as similar to a lossy compression scheme and wouldn't expect it to be further compressible to any significant extent using a general purpose lossless scheme. Similar to how general purpose compressors generally don't do very well with mp3s or jpgs.
- Deimorz 9y agoReducing the size by ~95% in exchange for a 0.001% error rate seems like a pretty nice tradeoff to be able to make for some uses. The nature of the data means it can never really be "perfect" anyway (there are certainly some password breaches that exist but aren't included in the list), so massively reducing the resources required in exchange for a bit of artificial error seems pretty reasonable to me.