Probabilistic Filters By Example
bdupras.github.io
bdupras.github.io
> HTTP/2 frame type to allow clients to inform the server of their cache’s contents. Servers can then use this to inform their choices of what to push to clients.
http://httpwg.org/http-extensions/draft-ietf-httpbis-cache-d...
https://h2o.examp1e.net/configure/http2_directives.html#http...
E.G: you identify user has being x, so you push a unique content to it, and tell to cache. Then later, you have a 62% of change some browser is user x. You just check if it's using the cached version of not. It will confirm at least if it's user x.
Edit: also as is written in the document, Cuckoo Filters and Bloom filters are not adapted to unbounded streams. Better options may include, for instance, Stable Bloom Filter[1] and block-Decaying Bloom Filter[2]
[0]: http://cglab.ca/~morin/publications/ds/bloom-submitted.pdf
[1]: http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDetExt.pdf
[2]: https://link.springer.com/article/10.1007/s11390-008-9192-1
n = 1, k = 2, m = 2
I.e. if a saturated filter were acceptable, there are 3 states: 01, 10, 11. These have, respectively, a 1 in 3, 1 in 3, and 3 in 3 false positive chance, for a total of 5 in 9 (I assume the 5 in 8 from the paper is a typo). But actually there are only 2 valid states: 01, 10. The valid inputs are still 01, 10, 11, though, so the real false positive chance is 1 in 3.
Maybe I'm missing something.
However looking at theorem 3 in [0] I think the difference between "classic" and "real" FPR is small, especially for larger n and m. At the end of [0] is mentioned a study in which the authors could not reach the classic FPR in their simulations, but attributed this result to bad pseudorandomness of elements. [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure).
The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1). Same for the second element, which yields 16 different cases. Out of these 16 cases 10 will lead to a false positive.
Thanks, that makes sense. I was thinking of states the filter could be in and ignored the different paths to get there. Now that I've had a chance to look at [0], it's interesting, but doesn't seem to matter for Bloom filters used in the normal way.
> "Valid" configurations do not exist
Sure, you can use any numbers you want, even negative ones. I take a more practical view, since Bloom filters make assumptions about choice (or derivation) of parameters. Given those assumptions, the formula criticized in [0] seems to work. Specifically:
> [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure).
We know the FPR of any Bloom filter that actually exists. For a load factor l and number of hash functions k, it's l^k. The problem is that the FPR for the expected load factor of a set of parameters is lower than the expected FPR for those parameters, iff the expected load factor is greater than half. But the whole point of a Bloom filter is to have half the bits set; that's the magic that minimizes size and FPR.
In practice you won't often have an expected load factor of exactly half, due to rounding. Depending on how you handle that, and whether you use asymptotics or an exact calculation, some drift in FPR makes sense. It'll be negligible as long as you're targeting half, though. n = 1, k = 2, m = 2 is noticeably off because at 3/4 it has a much higher expected load factor.
Did you edit Wikipedia / add a reference to the paper?
> Cuckoo filters improve on Bloom filters by supporting deletion
The page implies that this is achieved by removing the fingerprint from the hash table, but presumably one cannot guarantee that another key doesn't share the same fingerprint. This would result in a false negative for that key and violate an essential characteristic of the data structure.
Perhaps there's a nuance of the implementation I've missed.
As for collisions, only a limited number of colliding entries can be inserted into a cuckoo - after which a subsequent insertion will knowingly fail. So say Alice and Bob hash out to the same values, and you've inserted 2 Alices and 1 Bob. When you delete one Alice, it doesn't matter which entry is removed - two entries still remain that hash to Alice and Bob.
Perhaps the nuance you mention is that the alternate bucket index for an entry is calculated only from the fingerprint, not from the entry data. This has the effect that even when multiple entries share fingerprints, any one can be removed. (Again, _only_ if the system requesting the delete positively knows that the entry was previously successfully inserted.) The other colliding entry will still be found on query and will generate a "maybe" response.
>Deletion does not have to clean the entry after deleting an item. It also avoids the “false deletion”....
An item's position in the table is derived from two things: a fingerprint (a constant-sized hash) and second hash (ranging over the table). Nothing prevents two or more items from colliding on both hashes and therefore being indistinguishable from each other.
If the number of items in such a collision exceeds twice the fixed bucket size then deletion may result in false negatives.
In most practical applications there will be no useful way to bound the number of collisions. The paper shows results with bucket sizes of 4 and 8, but I don't know what the real-world probabilities of breaching these limits would be.
When you want to remove x, you remove one of the two fingerprints, it does not matter which since they're the same. Next when you query y you will be sure to still have a positive answer.
Note that however the deletion won't necessarily make the filter forget about x. It will just clear some place in the structure.
My multiset was:
a, b, c, d, e, f, g, h, j, abc, def, asd, asds, 3g46stb6vy6vsyosyvosfsdfsdsah, oooooooooooooooo
I assume this is just a javascript bug in implementation, because previously the filter said it might be in the set, actually adding it to the set then gave a false negative when trying it again.
This is a down-side to cuckoos (and counting blooms) - even when the filter has reasonable capacity remaining, an entry can be denied due to collision with previous entries and saturation of their slots.
The UX on this demo could be better - e.g. not insert into the bloom unless the cuckoo insert is successful (to keep them from diverging). Also, a message indicating an unsuccessful insertion would be nice.
In some cases, like the when there's a high likelihood of duplicate entries, this can represent a catastrophic failure mode. This is a good point, and when I get around to updating the tutorial, I'll make note of this.
Regarding the failure mode, an insertion can be knowingly rejected without mutating the filter, so the filter remains useful for subsequent insertions and all reads, retaining all its guarantees. The only loss is the rejection of the item - in our case we used this as signal to rebuild the filter at a larger size.
unless the Cuckoo filter has any two filled buckets, right? Which is a pretty critical failure mode not mentioned here. (What do you do then, accept the small new false-negative likelihood? start over with another filter?)
Re multisets, yes cuckoo filters and counting blooms are bounded - cuckoos by entries or bucket x 2, and blooms by bits per counter. Cuckoo's counting capability is more a side effect of the design. It's really only interesting in that you get limited counting in roughly the same bit space as a non-counting bloom. I suppose you could add counting bits to a cuckoo to support higher bounds in a similar manner to counting blooms.
I'm curious to hear more on your point on K-hashing in bloom filters - would you expand on your statement about only needing a K-bit hashing function? I'm happy to update the text on the tutorial to be more clear/exact.