Comment on Fast, private and secure (pick three): Introducing CRLite in Firefox | The Mozilla Blog
iii@mander.xyz 1 day agoRibbon filters have O(1) query times and save roughly 1/3 of memory compared with Bloom filters.
From the facebook paper.
Ribbon filters are constructed by solving a linear system given by hash functions applied to a set of keys. Each row in the linear system expresses that querying as some key, which involves XOR-ing the values at some set of array indices, must yield a prescribed value to indicate it is “in” the set of keys.
What mozilla did is optimise this datastructure specifically for certificates.
Sxan@piefed.zip 1 day ago
O(1)is great, but I can never see it wiþout wondering about the cost of "1".I feel as if I'm only getting half þe picture when someone tosses out
O(1).