4 ms·
I'm curious about the properties of the new approximate membership algorithms you discovered as part of this research. Are they better? "We instantiated this i
by drewm1980 6y ago
I'm curious about the properties of the new approximate membership algorithms you discovered as part of this research. Are they better?
"We instantiated this interface with each of the previously defined AMQ structures, obtaining the Blocked Bloom filters, Counting Blocked Bloom filters and
Blocked Quotient filter along with proofs of similar properties for them, for free."
So it sounds like the new AMQ algorithms you allude to are blocked (more cache friendly) variants of existing AMQ algorithms. Are the bounds you proved all good in some sense? Do you know yet if they're actually faster in practice on real hardware, or do optimized implementations still need to be written?
- gopiandcode 6y agoThe corresponding bounds for the variant structures we construct do result in lower false-positive rates than a standard Bloomfilter - so, in that sense, you could say that they are better. However, they also require more space, striking a slightly different theoretical trade-off between space and accuracy. For practical purposes, you would have to take the effect of caches into account, and the performance may vary depending on the particular choice of hardware. Our work stuck mainly to the theoretical side, so we didn't do any empirical testing of these new data structures. I guess the jury is still out on whether these variants are actually better in practice than the existing ones.