4 ms·

There is also quotient filter that has theoretical analysis and implementation (1). Also smaller than bloom filter and lets you delete. (1) https://github.com

• dgacmu 10y ago
  Quotient filters are cool, but are both modestly less memory-efficuent and quite a bit slower than Cuckoo filters. Their advantage is primarily theoretical -- Cuckoo filters force a minimum false positive rate that grows with logN/4 (I.e., if you insert 2^32 items, you must use at least 8 bits per item inserted). In practice, that's usually not much of a problem, but its why we say the Cuckoo filter is best for applications where you want a 1% or lower false positive rate. (disclosure: I'm one of the inventors of Cuckoo filters. Happy to answer questions about them, and very excited to see theoretical progress on them!)