Re:Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]
by pickledish on Monday October 24, 2022 @06:57PM
(#33323742)
This was an excellent post, learned a lot, thanks for linking it!
Re:Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]
by gsaussy on Monday October 24, 2022 @11:51PM
(#33325978)
True. I suspect improved filter performance is most useful for database development where preventing a read from unnecessarily hitting disk is the name of the game.
Re:Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]
by vlmutolo on Tuesday October 25, 2022 @12:14AM
(#33326148)
This is one of the things Cuckoo filters do well: they need either one or two memory accesses per query, compared to a Bloom filter which needs k accesses (where k is typically greater than 5).
Re:Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]
by hinkley on Tuesday October 25, 2022 @03:00AM
(#33327137)
We have a big collective blindspot about the implications of order of complexity when you get down to O(nlogn), and to a lesser extent anything in the neighborhood of O(nān), which is rarer but does happen.
A logn slowdown versus a linear speedup of two orders of magnitude - or more - is a set of lines that don't cross for any value of n any of us will see in our lifetimes, even if you're highly placed at a FAANG. The entire output of data from CERN throughout its entire history is a rounding error compared to n = 2^100.
And the fact of the matter is that long before n = 2^100, all of those constant time calculations we count on in Knuth's model of orders of complexity go from O(1) time to O(logn) anyway, so there is no such thing as an O(1) or O(n) algorithm when you have to represent everything as bignums.
https://blog.cloudflare.com/when-bloom-filters-dont-bloom/