Probabilistic Data Structure Showdown: Cuckoo Filters vs. Bloom Filters

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by thenewwazoo on Monday November 28, 2016 @03:36PM (#13058184)

To 1, they answer this in the paper; one knows it because

The xor operation in Eq. (1) ensures an important property: h1(x) can also be calculated from h2(x) and the fingerprint using the same formula. In other words, to displace a key originally in bucket i (no matter if i is h1(x) or h2(x)), we directly calculate its alternate bucket j from the current bucket index i and the fingerprint stored in this bucket by

    j = i ⊕ hash(fingerprint).

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by blauditore on Monday November 28, 2016 @04:12PM (#13058462)

Thanks. That's quite nice, but also reduces available hashing functions to pairs with that property. But I guess that's not really a problem.

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by dgacmu on Tuesday November 29, 2016 @07:38AM (#13062654)

If I'm understanding your comment right, you mean that the underlying cuckoo hash table can only use 2 buckets per item, right? We actually generalized this, but only in Bin's thesis:

https://www.cs.cmu.edu/~binfan/thesis/thesis_ss.pdf

See section 4.5. It was a bit more computationally expensive, so we didn't push forward with it in our implementation, as "2,4" cuckoo hash tables (2 hash functions to identify buckets, 4 associative elements) performed so well already.

[ Parent | on HN ]