2
$\begingroup$

The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and their implementation also enforces that (https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L90). This means that the load factor can be as bad as ~50%, depending on the number of keys.

The reason seems to be intrinsic to the alternate index algorithm: it is $$ h_2(x) = h_1(x) \oplus hash(signature) $$ The XOR makes the algorithm an involution (so the same formula holds to find $h_1$ from $h_2$), but the result is smaller than the table size only if the size is a power of 2.

Is there an alternative formula that works with non-powers of two? Basically something that pseudo-randomly maps signatures to involutions of [0, n).

$\endgroup$

2 Answers 2

1
$\begingroup$

Yes, it is possible. Use

$$h_2(x) = \text{hash}(\text{signature}) - h_1(x) \bmod n.$$

The theory behind this: if $c$ is a constant, the function

$$f(t) = c - t \bmod n$$

is an involution for any $c$ and any $n$, since

$$f(f(t) = c - (c-t) = t \pmod n.$$

Therefore, we can use the hash of the signature as the constant $c$. This gives you a scheme that works for any $n$, without requiring that $n$ be a power of two.

$\endgroup$
1
  • $\begingroup$ Ha, it was so simple in retrospect :) $\endgroup$ Sep 30, 2017 at 2:50
0
$\begingroup$

If you don't mind doing a test, check whether the current position is in $[0\,\mathpunct{\ldotp\ldotp}n/2)$ or $[n/2\,\mathpunct{\ldotp\ldotp}n)$, and depending on that add or subtract a random number in $[0\,\mathpunct{\ldotp\ldotp}n/2)$ derived from the signature. It's not completely random, but I guess it should work.

You can do the same with other tests, e.g., even/odd. You just add a random odd number based on the signature (even case) or subtract it (odd case).

$\endgroup$
2
  • $\begingroup$ That's an interesting suggestion. You lose one bit this way, in that the alternate index can only reach half of the positions in the table. It's not obvious to me that this is random enough to have the Cuckoo algorithm converge. $\endgroup$ Sep 29, 2017 at 18:05
  • $\begingroup$ On a second thought, this seems pretty much equivalent to using the original formula, but xoring with $hash(signature)$ truncated to $\lfloor \log(n) \rfloor$, which would still make it land within the table. However the same concern holds, I'm not sure if this shuffles things around enough to make Cuckoo happy. $\endgroup$ Sep 29, 2017 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.