Hacker News Reader

Comment by honoredb | Hacker News Reader

But that's still 12G of memory, since you can't compress it. Is there a data structure that's better optimized for space and probabilistic membership tests?

View on HN

Cuckoo Filter:

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Cuckoo filters and bloom filters are different in how they handle increased load. As the cuckoo filter increases load, insertions are more likely to fail, and so its time complexity increases exponentially. However, the false positive rate remains the same. Bloom filters can keep inserting items into the filter at the cost of an ever rising false positive rate.

https://brilliant.org/wiki/cuckoo-filter

you can compress it by just truncating the hashes as short as you want

I think the method you're describing is equivalent to a bloom filter that only uses one hash function per key.

its the same structure as a Bloom filter but more efficient because it has no empty slots

No, it's not the same structure as a Bloom filter without empty slots. It's the same structure as a Bloom filter with only one hash function. Bloom filters use multiple.

multiple hash functions only exist because they don't use secure hashes (for speed reasons) so there's collisions.

Normally for passwords you would use a secure hash, negating this

No, the math on bloom filters already assumes a random oracle.

To store 500 million hashes in 860MB, wouldn't you need to truncate them to 13 bits each? That'd give a false positive rate of 1000 in 1000, slightly worse than the Bloom filter's false positive rate of 1 in 1000.

Depends on the data structure and encoding. For instance, another simple/fast/non-optimal encoding would be a 32 bit table of bit flags, which would weigh in at 0.5 GiB. That would give you a ~11.5% false positive rate.

Reply on news.ycombinator.com