3
$\begingroup$

Question

I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs:

  1. There are over $n = 30 000$ first names that exists in the whole world
  2. I have a Cuckoo filter storing the names of people who gave me a gift at least once
  3. I am certain that the Cuckoo filter will not have to store more than 600 names
  4. The names the Cuckoo filter will store are evenly distributed across the 30 000 names
  5. Of course the final goal is to be able to know which names gave me a gift at least once, I might have to query for any of the 30 000 names.

I would like to design my filter for 600 elements; however the original paper about Cuckoo filters considers that the number of buckets $m$ is a multiple of $n$.

Now consider a construction process that inserts $n$ random items to an empty table of $m=cn$ buckets for a constant $c$

Am I supposed to size the filter according to set of all names in the world ? Is there something I am missing ? This is not addressed in the original publication.

Constraints

Size : The Cuckoo filter will be transmitted over the network. But it will be done in an asynchronous way (let's say an update every 2 hours). So this will weigh in the size constraint.

Time : The real constraint is time. When I query the filter I would like my response in less than 5 seconds.

False positive : I also hope to have false positive rate of at most 20%.

Security : In my example I store names, but in reality I will store sensitive data that should be protected and anonymized under GDPR. After a statistical analysis I concluded that the data's entropy is too low to store as a list of hashes.

Other options : I'm open minded by nature. I always welcome other options.

Attempt at a self answer

Considering that the fingerprint is $f$ bits long, and I have $m$ buckets, the probability that the name Bob has the same features (index and fingerprint) as the name Alice is :

$$ \frac{1}{2^f} \cdot \frac{1}{m} $$

Which means that the probability that there is another name colliding with the name Anna is:

$$ (n - 1) \cdot \frac{1}{2^f} \cdot \frac{1}{m} $$

With 30 000 names, a fingerprint of 8 bits and 600 buckets, the result is $0.39$ which means a false positive rate of 39 %.

To reduce the false positive rate I can either increase the fingerprint size or the number of buckets. Using 6000 buckets instead of 600 gives me a false positive rate of 3.9%. This hack might be working in my example case but in reality we are talking of $10^{19}$ names in the whole world and $10000$ names to store in the filter.

It seems to me that Cuckoo filter were not designed with this use case in mind, and when people are using Cuckoo filter, they hope to store almost every existing item in there at some point.

$\endgroup$
18
  • $\begingroup$ The number of possible names shouldn't factor in. It could be infinite. The relevant number is 600. $\endgroup$ Apr 6 '20 at 9:24
  • $\begingroup$ If Anna and Bob collide (same fingerprint and index). I add Anna to the filter. I query the filter for Bob. I get a false positive. I guess I don't see how I cannot factor the number of possible names in this. $\endgroup$
    – braincoke
    Apr 6 '20 at 9:26
  • $\begingroup$ You might be right. In that case, it is certainly true that you are "supposed to size the filter according to set of all names in the world", so I'm not quite sure what your question is. $\endgroup$ Apr 6 '20 at 9:28
  • $\begingroup$ It might help to give a pointer to Cuckoo filters, and explain how exactly you are planning to use them, and what guarantees you are after. $\endgroup$ Apr 6 '20 at 9:29
  • $\begingroup$ The use case is exactly what I described in the question, I am looking to get the best false positive rate possible, at least 90%. $\endgroup$
    – braincoke
    Apr 6 '20 at 9:32
1
$\begingroup$

As discussed in the comments it turns out that, yes, I need to size my Cuckoo filter for the set of every existing name. That being said, it is not much of a problem in the end if I only send the buckets with fingerprints in it, which shouldn't be more than 600.

In addition to that, my attempt at a self answer was very wrong. The probability that there is another name colliding with the name Anna is actually:

$$P\left(\bigcup_{i = 1}^n A_i\right) = \sum_{k = 1}^n (-1)^{k+1} \sum_{1 \le i \lt j ... \lt k \le n} P(A_i \cap A_j ... \cap A_k)$$

This is the inclusion-exclusion principle. Because of my hypotheses, the probability can be simplified as:

$$P\left(\bigcup_{i = 1}^n A_i\right) = 1 - (1 - p)^n$$

As highlighted in the original paper, we also have to take into account that $$2b/2^f \le \epsilon$$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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